Esta es mi página web por los tareas de la asignatura “Geometría Computacional”.

Note: I know that this page is quite a bit of a mess. Please forgive me, but the practical project (linked below) kept me quite busy during the course and I didn’t consider maintaining this page (which basically meant retyping my handwritten notes form class) as the most important thing to do. So in case you can’t find what you need here, just go to the official course homepage (also linked below).

Contents

1 Programa del Curso
2 Proyecto Práctico
3 Descargas (Código)
4 Problemas Tratados
4.1 Problemas Básicos
4.2 Polígonos y Poliedros
4.2.1 Polígonos I
4.2.2 Definiciónes
4.2.2.1 Estructuras de datos
4.2.2.2 Problemas
4.2.3 Polígonos II
4.2.3.1 Clases particulares de polígonos
4.2.3.2 Problemas
4.2.4 Triangulación (de Polígonos)
4.2.4.1 Triangulaciónes
4.2.4.2 Aplicaciones de la triangluación
4.2.4.3 Problemas
4.3 Cierres Convexos
4.3.1 Definición
4.3.2 Algorítmos
4.3.3 Aproximación
4.3.4 Envolvente Convexa Ortogonal
4.3.5 Aplicaciones de Cierre Convexo
4.4 Triangulaciones de Nubes de Puntos
4.4.1 Triangulación de Delaunay
4.4.2 Problemas de Proximidad
4.5 Diagramas de Voronoi
4.6 Arreglos de Rectas, Dualidad
5 Enlaces

Programa del Curso

1. Introducción a la Geometría Computacional. Terminología y herramientas básicas.
2. Polígonos y poliedros. Localización. Triangulación de polígonos. Aplicación a problemas de visibilidad.
3. Cierres convexos: de una nube de puntos y de polígonos. Aplicaciones: Diámetro, anchura, pares antipodales.
4. Triangulaciones de nubes de puntos. Triangulación de Delaunay. Problemas de proximidad.
5. Diagramas de Voronoi.
6. Arreglos de rectas. Dualidad.

Proyecto Práctico

Mi tema fue el desarollo de una aplicación para la triangulación de polígonos con “agujeros“.

• La aplicación es “open source” y se encuentra en CodePlex [Link].
• La página web oficial de mi programa está aquí [Link].

Descargas (Código)

• Biblioteca de implementaciones de las soluciones del curso (Proyecto Visual Studio 2005)
• Documentación del código (Generado automáticamente con Doxygen)
• Notas de clase en formato PDF

Problemas Tratados

Problemas Básicos

Búsqueda de extremos

• Hallar el punto con mayor abscisa.
• Dada un vector, hallar el extremo según la dirección de ese vector.
• Hallar el rectángulo mínimo de lados paralelos a los ejes que contiene a todos los puntos.

Ordenaciones

• Ordenar los puntos segun sus abscisas de menor a mayor.
• Ordenar los puntos según una dirección dad por un vector.
• Ordenar los puntos angularmente respecto de un punto dado y en sentido positivo, comenzando por el de menor ordenada.

Búsqueda en rangos

• Escribir un algoritmo que calcule, para cada rectángulo de lados paralelos a los ejes, el número de puntos del conjunto que contiene.

Polígonos y Poliedros

• Localización
• Triangulación de polígonos
• Aplicación a problemas de visibilidad

Polígonos I

Definiciónes

• Polígono
• Polígono simple
• Polígono convexo

Estructuras de datos

¿Cómo representar un polígono?

Problemas

• Hallar el área de un polígono.
• Averiguar si un polígono es convexo.
• Localizar un punto respecto de un polígono (¿dentro o fuera?).
• Localizar un punto respecto de un polígono convexo.
• Hallar un polígono cuyos vértices sean unos puntos dados (poligonización).

Test de intersección

• Averiguar si dos rectángulos se cortan.
• Averiguar si una recta corta a un polígono convexo.
• Averiguar si una recta corta a un polígono.
• Averiguar si dos polígonos convexos se cortan.
• Averiguar si dos polígonos se cortan.

Polígonos II

Clases particulares de polígonos

• Convexos
• Monótonos
• Estrellados
• Espirales
• Otros

Problemas

• Algoritmo para reconocer un polígono convexo.
• Algoritmo para reconocer un polígono monótono en la dirección OX.
• Algoritmo para reconocer un polígono monótono.
• Algoritmo para reconocer un polígono estrellado.
• Algoritmo para reconocer un polígono espiral.
• Localización de un punto en cada uno de los casos especiales de polígonos.
• Poligonización de puntos.

Triangulación (de Polígonos)

Triangulaciónes

• Algoritmo “Brute Force” – O(n³)
• Metodo de otectomía – O(n²)
• Caso particular: Polígonos monótonos
• Triangluación de Delaunay
• Triangulación del interior y exterior de un polígono

Aplicaciones de la triangluación

• Triangular la región comprendida entre 2 polígonos PCQ
• Problema de la galeria de arte: n/3 vértices vigilan el interior de un polígono
• Polígono de visibilidad en O(n)
• Operaciones booleanas en O(n²)
• Rendering
• Elementos finitos

Problemas

• ¿Es conexo el grafo de las triangulaciones de un polígono mediante flip de aristas?

Cierres Convexos

Definición

Algorítmos

• Búsqueda de aristas
• Búsqueda de aristas (más inteligente) (Jarvis)
• Algoritmo de barrido
• Algoritmo de Graham
• Algoritmo de Andrew
• Divide y vencerás

Aproximación

• Aproximación por defecto
• Aproximación por exceso

Envolvente Convexa Ortogonal

• Definición: Conjunto Ortoconvexo
• Definición: Evolvente Convexa Ortogonal
• Hallar el Cierre Convexe de una Lista de Puntos
• Hallar el Cierre Convexe de una Lista de Puntos (Alternativa)
• Problema de las Farolas

Aplicaciones de Cierre Convexo

• Movimientos
• Calculo de la Recta Centro
• Cierre Convexo de Discos
• Expansión de Figuras
• Capas convexas

Triangulaciones de Nubes de Puntos

Triangulación de Delaunay

Problemas de Proximidad

Diagramas de Voronoi

Arreglos de Rectas, Dualidad

Enlaces

Directamente relacionada a la asignatura

• Página web de la asignatura [Link]

Relacionada al tema “Geometría Computacional” en general

Software

• CGAL – Biblioteca de algoritmos para geometría computacional [Link]
• Cabri – Aplicación para la visualización geométrica [Link]

Información

• Página web sobre el tema “Voronoi” [Link]
• Página web con una lista de alogritmos de la geometría computacional [Link]