Algoritmo para completar una triangulación parcial (Triangulación limitada)

Question

Dado un conjunto de puntos en un plano y un triangulation of the convex hull of the points incompleto (solo se proporcionan algunos bordes), estoy buscando un algoritmo para completar la triangulación (los bordes dados inicialmente deberían permanecer fijo). Puede suponer que es posible completar la triangulación parcial, pero sería genial si también pudiera sugerir un algoritmo para verificarlo también.

ACTUALIZACIÓN "Se le da un casco convexo de un conjunto de puntos R^2, que es básicamente un polígono con algunos puntos en su interior. Queremos triangular el conjunto de puntos que es una cuestión directa en sí misma, pero también se le dan algunos bordes que cualquier triangulación que se le ocurra debería usar esos bordes ".

Answer 1

Quizás esta sea una respuesta ingenua, pero ¿no puede simplemente usar una triangulación de delaunay restringida? Agregue los bordes conocidos como restricciones.

CGAL tiene un nice implementation. La herramienta triangle tiene características similares y es más fácil de empezar, pero tiene (quizás) un poco menos de flexibilidad.

Answer 2

Descubrí que el libro "Geometría Computacional: Una Introducción" tiene un tratamiento detallado del tema aunque no da un pseudo-código listo para implementar.

El algoritmo más fácil es uno codicioso que enumera todos los bordes posibles y luego los agrega uno por uno evitando la intersección con las edades previamente agregadas. Hay una larga discusión en el libro sobre cómo reducir el tiempo de ejecución a O (n^2 log n).

Luego hay un algoritmo O (n log n) que primero regulariza el casco convexo con los bordes dados y luego triangula individualmente cada polígono monótono.