Software sobre Geometría Computacional

Desde 1988 se realizaron, en el Departamento de Matemática Aplicada de la entonces Facultad de Informática de la UPM, Trabajos Fin de Carrera dentro del campo de la Geometría Computacional y dirigidos por los profesores Manuel Abellanas Oar y Gregorio Hernández Peñalver. Como fruto de estos trabajos se obtuvieron aplicaciones que implementaban algoritmos que resolvían distintos problemas del área.

Las implementaciones se realizaron en diferentes lenguajes de programación. A partir del año 2000, las applets o aplicaciones Java permitían ejecutar directamente en la red los programas, pero los trabajos anteriores al 2000 necesitan descargar la aplicación, instalarla en el propio ordenador y ejecutarla. A continuación, se presentan, agrupados por temas y comprimidos en uno o varios archivos, los programas desarrollados en estos años.

Debido a cambios en el servidor los programas no son accesibles vía web. Si está interesado en alguno de ellos puede solicitarlos mediante un email a
gregorio.hpenalver@upm.es

Cierre Convexo y Aplicaciones en 2-D

  • Un programa con casi todos los algoritmos de cálculo del cierre convexo de una nube de puntos se encuentra en los archivos disco1.zip, disco2.zip y disco3.zip. Una vez descomprimidos necesita instalación. (Juan Manuel Garrido)
  • akl_tous.zip presenta (en MS-DOS) el algoritmo de Akl y Toussaint.
  • calibres.zip es una implementación (en MS-DOS) de un algoritmo para calcular la anchura de un conjunto de puntos por el método de los calibres. (Emilio Aguilar, 10-94)
  • bisector.zip presenta un algoritmo para calcular el bisector óptimo de una nube de puntos. (Israel Martín, 11-96)
  • puntmax.zip implementa (en MS-DOS) los algoritmos para calcular los puntos maximales orientados y no orientados de nubes de puntos y de polígonos. (Ángel Arroyo, 19-2-96)
  • PMaximalWin.zip presenta varios algoritmos para calcular los puntos maximales de una nube de puntos. (Pedro Fidel Sánchez, Miguel Ángel Valero, 9-98)
  • ortoconv.zip presenta varios algoritmos para calcular el cierre ortoconvexo de polígonos ortogonales. (Juan Carlos Marcos, 18-5-98)
  • En el archivo LeeMelkman.zip se encuentra un programa con los algoritmos de Lee y Melkman para obtener el cierre convexo de un polígono. Una vez descomprimido necesita instalación. (Sonia Ochando, 25-6-99)
  • Recta centro. Se resuelve el problema de localizar la recta que minimiza la distancia máxima a una nube de puntos en el plano. (José I. Fernández, 10-4-02)
  • Cierre convexo. Implementación en Java de los algoritmos de Graham, jarvis y divide y vencerás para el cálculo del cierre convexo de una nube de puntos. Además construye las capas convexas y la triangulación correspondiente. (Marcos A. Niño, 11-02-05)

Polígonos

  • geowin.zip construye diferentes poligonizaciones (estrellada, monótona, monótona semiconvexa, cebolla) de una nube de puntos. (Patricia Mantecón, 3-93)
  • polvacio.zip construye, dada una nube de puntos, todos los polígonos convexos de r lados cuyos vértices son puntos de la nube y que no contiene en su interior ningún punto de la nube. (Fernando Razola, 30-1-96)
  • Camino mínimo en un entorno poligonal. Construye el camino de longitud mínima que debe seguir un robot puntual en presencia de obstáculos poligonales. (Nuria Navarro, 7-9-01)
  • Partición de polígonos en piezas convexas. Descompone un polígono en polígonos convexos siguiendo el algoritmo de Hertel y Mehlhorn. (Esther Lameiro, 21-6-02)
  • Sumas de Minkowski de polígonos. Herramienta para el cálculo y la visualización de la Suma de Minkowski de dos polígonos cualesquiera. (Gustavo Kavka y Mª Teresa Taranilla, Departamento de Informática, Universidad Nacional de San Luis, Argentina. 31-7-02)
  • reco_pol.zip detecta si un polígono dado es monótono o estrellado. (Javier Méndez, 28-7-04)

Búsqueda en Subdivisiones Planas

  • kirkpat.zip presenta el algoritmo de Kirkpatrick de búsqueda en subdivisiones planas. (El archivo kirk16.exe se ejecuta en Windows 3.1 y kirk32.exe en Windows 95). (Raúl Cecilia, 19-9-97)
  • LSM-Programa.zip implementa los algoritmos de localización en subdivisiones planas basados en la descomposición en regiones monótonas.
  • Algoritmo de Kirkpatrick de localización de puntos en triangulaciones (en Java). (Gema Perez Perales, 3-03)

Triangulaciones de Polígonos. Aplicaciones

  • Un programa con casi todos los algoritmos de triangulación de polígonos se encuentra en los archivos tripol1.zip y tripol2.zip. Una vez descomprimidos en el mismo directorio necesita instalación (Mª Ángeles Almodóvar y Lorenza López, 4-12-00)
  • tri_leda.zip triangula un polígono por el algoritmo de Garey-Johnson, utilizando la biblioteca LEDA. (Mariano Sanz, 1-96)
  • mangas.zip implementa dos algoritmos de triangulación de polígonos: el algoritmo de Kong, Everett y Toussaint de poda de orejas y el algoritmo de Toussaint de mangas. (Rafael González, 21-2-97)
  • camino_m.zip construye, a partir de la triangulación el camino de longitud mínima entre dos puntos cualesquiera de un polígono. (Carlos Gómez, 25-3-99)
  • PolVisLado.zip construye, a partir de la triangulación, el polígono de visibilidad desde un lado. (Rocío Vázquez, 5-10-99)
  • caminogeodesico.zip construye los caminos geodésicos entra cada par de puntos en el interior de un polígono. (Jaime González, 21-7-00
  • Triangulación de Delaunay de un polígono. Construye la triangulación de Delaunay de un polígono mediante flips a partir de la triangulación por otectomía. (Laura Blázquez, 9-7-02)

Diagramas de Voronoi y Triangulaciones de Delaunay en 2D

  • voronoip.zip presenta varios algoritmos (incremental, divide y vencerás, etc.) para construir el Diagrama de Voronoi de una nube de puntos sin pesos asociados o con ellos (diagrama de potencias). También construye la triangulación de Delaunay. (Todo ello en MS-DOS). (Juan Andrés Hermoso, Raúl Rodrigo, Ramón Revuelta, 6-95)
  • fortune.zip presenta el algoritmo de barrido de Fortune para construir el diagrama de Voronoi de una nube de puntos. (Oscar Morales, 10-96)
  • isolinea.zip construye las curvas de nivel de una superficie a partir de una nube de datos puntuales sobre ella. (Jesús Mouriz, 1-95)
  • En los archivos flips1.zip, flips2.zip y flips3.zip se encuentra un programa que construye la triangulación de Delaunay de una nube de puntos con el algoritmo de intercambio de aristas (flips). Una vez descomprimidos necesita instalación. (Javier Larrauri, 11-97)
  • Diagrama de Voronoi. Algoritmo de Fortune. Visualización interactiva del algoritmo de barrido para la construcción del Diagrama de Voronoi de una nube de puntos. (Juan Carlos Ferreras, 29-12-00)
  • En el archivo voronoiL1.zip se encuentra un programa que construye el diagrama de Voronoi para la métrica L1. (Jesús Barrios, 6-7-01)
  • Intercambio de aristas en grafos geométricos. Estudian los “flips” o intercambios de aristas sobre varios grafos geométricos: triangulaciones de Delaunay de una nube de puntos, cadenas poligonales y polígonos convexos. (Ulises Berzal y Jorge de Diego, 24-7-01)
  • Diagrama de Voronoi. Círculos creciendo. Muestra la construcción del Diagrama de Voronoi (y la Triangulación de Delaunay) de una nube de puntos en el plano observando el crecimiento de la zona de influencia de cada punto. (Fernando Mena, 24-2-03)
  • Modelización del terreno mediante Triangulacion de Delaunay. Muestra las curvas de nivel y los diferentes perfiles de un terreno a partir de la triangulación de Delaunay de una muestra de puntos del terreno. (Juan A. Hortigüela, 24-2-03)
  • Triangulación de Delaunay con diferentes métricas. Utilizando la propiedad de que las aristas Delaunay están contenidas en círculos vacíos de puntos de la nube, esta aplicación permite obtener “a mano” la triangulación de Delaunay con diferentes métricas. (David Íscar, 22-2-02)
  • Diagrama de Voronoi lejano. Construye el Diagrama de Voronoi de orden n-1 o Diagrama de Voronoi lejano. (Manuel Romero, 4-12-02)
  • Furthest Point Voronoi Diagram. Construye el Diagrama de Voronoi lejano y el mínimo círculo que contiene una nube de puntos. (Paul Herron, 15-9-03)

Triangulaciones de Nubes de Puntos

  • trinubes.zip presenta varios algoritmos para construir triangulaciones de nubes de puntos en 2D (Los algoritmos implementados son: fuerza bruta, abanico, incremental, Delaunay, inserción de aristas). (Tomás Olivera, 11-01)
  • Triangulaciones de nubes de puntos. Muestra (en Java) varios algoritmos para triangular nubes de puntos en el plano: Abanico, incremental, divide y vencerás y triangulación de Delaunay. (Luis Manuel Arteaga, julio 2002)
  • Pseudotriangulaciones de nubes de puntos y de polígonos. Para nubes de puntos construye pseudotriangulaciones mediante los algoritmos de barrido, incremental, por capas convexas y a partir de una triangulación. Para un polígono presenta dos algoritmos: a partir de caminos mínimos y desde una triangulación elegida del convexo con el mismo número de vértices. (Julio A. Quicios García, junio 2011).
    En la memoria hay información exhaustiva sobre pseudotriangulaciones

Visibilidad e Iluminación

  • polvis.zip calcula el polígono de visibilidad desde un punto interior a un polígono (en MS-DOS).
  • polvisw.zip (lo mismo que el anterior bajo Windows). (Mercedes Domínguez, 19-2-96)
  • mirar_tr.zip presenta diferentes algoritmos que resuelven problemas de optimización del ángulo de visión, cuando se mira a través de diferentes objetos geométricos (segmentos, polígonos, circunferencias). (José Manuel Barrientos, 27-6-95)
  • espiral.zip presenta algoritmos para colocar guardias de diferentes tipos en polígonos espirales (en Ms-Dos). (Rafael Pelacho, 4-10-95)
  • p_oculto.zip presenta algoritmos para ocultar puntos en una nube de segmentos (en Ms-Dos). (César Castillo, 27-3-95)
  • prision.zip coloca adecuadamente los guardias en prisiones monótonas. (Manuel Camacho, 27-3-95)
  • rutas_ve.zip calcula la ruta de longitud mínima que debe seguir un guardia para vigilar el exterior de algunos tipos de polígonos. (Arturo Rodríguez, 3-12-97)
  • En los archivos GrafVis1.zip, GrafVis2.zip, GrafVis3.zip y GrafVis4.zip se encuentra un programa que implementa dos algoritmos sobre grafos de visibilidad. El primero construye el modelo de arcos del grafo de visibilidad de un anillo poligonal. El segundo construye un polígono monótono a partir de su grafo de visibilidad. Una vez descomprimidos los archivos el programa necesita instalación. (Esther Navarro, 4-5-98)
  • En los archivos ilumconv1.zip e ilumconv2.zip se presenta un algoritmo sobre iluminación de polígonos convexos. Se resuelve el problema de los dos reflectores. Una vez descomprimidos los archivos el programa necesita instalación. (José Antonio Martín, 23-6-98)
  • En los archivos fortaleza1.zip y fortaleza2.zip se presenta el Problema de la Fortaleza, vigilancia exterior de un polígono, tanto en el caso general como en el particular de polígonos ortogonales. Una vez descomprimidos los archivos el programa necesita instalación. (Juan Antonio Blanco, 23-11-99)
  • En el archivo GaleriaArte.zip se presenta el Problema de la Galería de Arte para diferentes tipos de polígonos: monótonos, estrellados, espirales y generales. (Mª Esther Martínez y Carlos Gargallo, 21-12-99)
  • MaxVisibilidad.zip determina el punto de visión óptimo para mirar un objeto o para mirar entre obstáculos cuando el punto de visión recorre una trayectoria. (Juan R. Aparicio, 11-6-01)
  • Vigilancia de polígonos con guardias-lado. Visualización del Problema de las Galerías de Arte para polígono monótonos y guardias que patrullan por los lados del polígono. (Miguel Ochoa Fuentes, 28-2-01)
  • Iluminación óptima de polígonos con métodos heurísticos. Calcula el punto interior del polígono que ilumina la máxima área, mediante los métodos del gradiente y fuerza bruta. (Adolfo Fernández, 11-12-03)
  • Iluminación de polígonos con reflectores. Una herramienta para contrastar hipótesis sobre iluminación de polígonos. Los reflectores tienen alcance y amplitud variables. (Bassam Al-Zarif Zabala, 23-05-05)
  • Iluminación de polígonos con reflectores ortogonales. Aplicación en Ms-Dos mostrando algoritmos para colocar reflectores ortogonales en polígonos ortogonales. (Manuel López-Menchero, 24-06-05)
  • Vigilancia en terrenos poliédricos. Herramienta para la vigilancia de diferentes triangulaciones de nubes de puntos mediante guardias-vértice o guardias-arista. (César González Vázquez, 26-09-17)

Descomposición de Polígonos Ortogonales

(Todos en Ms-Dos)

  • sack.zip presenta el algoritmo de Sack y Toussaint para descomponer un polígono ortogonal en cuadriláteros convexos. (Blanca Carballo, 11-7-95)
  • lubiw.zip presenta el algoritmo de Lubiw que permite descomponer un polígono ortogonal (sin agujeros o con ellos) en cuadriláteros convexos. (Alfonso Díaz-Regañón, 5-12-94)
  • eles.zip presenta el algoritmo de O´Rourke que descompone un polígono ortogonal en piezas en forma de “ele”. (Roberto Vaquerizo, 3-10-94)

Mosaicos

  • mosaico.zip genera cada uno de los 17 tipos de teselaciones periódicas del plano a partir de una imagen contenida en un archivo “.bmp” (Mª Teresa Sánchez, 5-99)

Arreglos

  • arreglos.zip construye un arreglo de rectas y calcula sus niveles. (Mª Concepción Fontalba, 10-99)

Geometría de Rectángulos

  • georect.zip estudia varios problemas sobre la unión de una familia de rectángulos, perímetro, contorno, superficie, etc. (Luis Pérez, 9-96)

Algoritmos Aleatorizados

  • En los archivos aleatoriz1.zip y aleato2.cab se presenta una implementación de algoritmos aleatorizados que resuelven los siguientes problemas:
    Mínimo disco que contiene una nube de puntos.
    Triangulación de Delaunay de una nube de puntos.
    Descomposición trapezoidal asociada a una nube de segmentos
    (Una vez descomprimido el primer archivo hay que instalar el programa)
    (Iván García, 30-11-99)

Grafos Geométricos

  • Arboles y círculos tangentes. Una vez dibujado un árbol, la aplicación averigua si es un grafo de monedas, calculando un conjunto de círculos, de interiores disjuntos, cuyo grafo de contactos es el árbol dado. (Carlos Moreno Jiménez, 24-7-01)
  • Intercambio de aristas en grafos geométricos. Estudian los “flips” o intercambios de aristas sobre varios grafos geométricos: triangulaciones de Delaunay de una nube de puntos, cadenas poligonales y polígonos convexos. (Ulises Berzal y Jorge de Diego, 24-7-01)
  • Empaquetamiento de círculos. Se estudian las configuraciones de círculos iguales de radio máximo contenidos en regiones rectangulares. (Enrique Bañales, 18-6-02)
  • Juegos geométricos con triangulaciones. Se plantean varios juegos de dos jugadores basados en las triangulaciones de nubes de puntos. (Beatriz Cortés, 26-5-04)
  • Ruteo en grafos geométricos. Diferentes estrategias de ruteo (greedy routing, compass routing, randomized compass routing, Voronoi routing, etc.) sobre triangulaciones de Delaunay, grafos de Gabriel y grafos de vecindad relativa (David Ramos, 19-7-04)

About Gregorio Hernández Peñalver

Profesor del Departamento de Matemática Aplicada a las TIC ETSI Ingenieros Informáticos, UPM (jubilado)