En geometría computacional , una triangulación de Delaunay restringida es una generalización de la triangulación de Delaunay que fuerza ciertos segmentos requeridos en la triangulación como aristas, [1] [2] a diferencia de la triangulación de Delaunay en sí misma que se basa puramente en la posición de un conjunto dado de vértices sin tener en cuenta cómo deben estar conectados por aristas. Se puede calcular de manera eficiente y tiene aplicaciones en sistemas de información geográfica y en la generación de mallas.
La entrada al problema de triangulación de Delaunay restringida es un grafo de línea recta plano , un conjunto de puntos y segmentos de línea que no se cruzan en el plano. La triangulación de Delaunay restringida de esta entrada es una triangulación de su envoltura convexa , que incluye todos los segmentos de entrada como aristas y utiliza solo los vértices de la entrada. Por cada arista adicional agregada a esta entrada para convertirla en una triangulación, debe existir un círculo a través de los puntos finales de , de modo que cualquier vértice interior al círculo esté bloqueado de la visibilidad desde al menos un punto final de por un segmento de la entrada. Esto generaliza la propiedad definitoria de las triangulaciones de Delaunay bidimensionales de puntos, que cada arista tiene un círculo a través de sus dos puntos finales que no contiene otros vértices. Siempre existe una triangulación que satisface estas propiedades. [1]
Jonathan Shewchuk ha generalizado esta definición a triangulaciones de Delaunay restringidas de entradas tridimensionales, sistemas de puntos y segmentos no cruzados y triángulos en el espacio tridimensional; sin embargo, no todas las entradas de este tipo tienen una triangulación de Delaunay restringida según su definición generalizada. [2]
Se conocen varios algoritmos para calcular triangulaciones de Delaunay restringidas de gráficos de líneas rectas planas en el tiempo . [1] [3] La triangulación de Delaunay restringida de un polígono simple se puede construir en tiempo lineal . [4]
En el levantamiento topográfico , se construye una triangulación a partir de puntos tomados en el campo. Si un borde de la triangulación cruza un río, la superficie resultante no modela con precisión la trayectoria del río. Por lo tanto, se dibujan líneas de quiebre a lo largo de ríos, bordes de caminos, crestas de montañas y similares. Las líneas de quiebre se utilizan como restricciones al construir la triangulación.
La triangulación de Delaunay restringida también se puede utilizar en los métodos de refinamiento de Delaunay para la generación de mallas , como una forma de forzar la malla a ajustarse a los límites del dominio a medida que se refina.
