Home

Geometría Computacional

           Geometría Computacional

Objetivo:

Se analizarán los principales algoritmos, desde su complejidad y realización, que se utilizan para manipular entidades geométricas en dos y tres dimensiones.

Contenido:

  1. Inducción matemática

  2. Triangulación de polígonos
    • El problema de la galería de arte
    • Cálculo del área de un polígono
    • Algoritmo de triangulación de complejidad O(n²)
    • Partición de un polígono es sus piezas monótonas-y
    • Algoritmo de triangulación de un polígono monótono-y de complejidad O(n log n)

  3. La cubierta convexa
    • Definiciones
    • Algoritmo de Graham
    • Algoritmo de Andrew
    • Algoritmo QuickHull
    • Análisis de complejidad

  4. Cálculo de la cubierta convexa en tres dimensiones

  5. Diagramas de Voronoi
    • El algoritmo de Fortune para construir el diagrama de Voronoi

  6. Triangulación de Delaunay

  7. Búsqueda e intersección
    • Intersección de línea contra línea
    • Intersección de línea contra triángulo
    • Intersección de linea contra cuadrilátero
    • Intersección de linea contra cajas

  8. Otros algoritmos de intersección

  9. Detector de colisiones para manipular objetos virtuales

Bibliografía:

  • Computational Geometry an introduction. F.P. Preparata. 1985. Springer
  • Computational geometry, algorithms and applications. 2nd edition. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. 2000. Springer.
  • Computational Geometry in C. 2nd edition. J. O'Rourke. 1988 Cambridge Tracts in Theoretical Computer Science.
  • Real Time Collision Detection. C. Ericson. 2005. Morgan Kaufmann
  • Collision detection in interative 3D enviroments. G. van den Bergen 2004. Morgan Kaufmann
  • share