Publicación:

Visualización de superficies en 3d por medio de diagramas de voronoi

Resumen

Este trabajo describe tres de las estructuras más importantes en la Geometría Computacional que son la Envolvente Convexa, el Diagrama de Voronoi y la Triangulación de Delaunay de una nube de puntos en el espacio. La mayor parte de los contenidos se basan en el texto de Geometría Computacional en C de Joseph O™Rourke A través del trabajo, se presentan de manera progresiva los algoritmos que permiten construir las estructuras mencionadas, hasta llegar a diseños óptimos en su tiempo de ejecución. En el primer capítulo se plantea el Problema de la Galería de Arte de Klee con el fin de enmarcar la importancia de la triangulación; una vez resuelto dicho problema, se procede a encontrar el algoritmo que realice la mejor partición de un polígono; este debe dividir dicho polígono en el menor número de partes convexas en el menor tiempo posible. En el segundo capítulo se define la envolvente convexa de una nube de puntos y se presentan los algoritmos que permiten calcularla. En el tercer capítulo se define el Diagrama de Voronoi de una nube de puntos, su estrecha relación con la triangulaciones de Delaunay y se presenta un código en lenguaje C con el cual se puede calcular el diagrama de Voronoi en el plano, apoyándose en su triangulación de Delaunay, obtenida mediante el cálculo de la envolvente convexa de la proyección de dichos puntos sobre un paraboloide. El trabajo finaliza con la presentación de un algoritmo que permite visualizar el comportamiento de un frente de onda en determinada superficie.