Estoy implementando el algoritmo Bowyer-Watson como se presenta enWikipedia. En mi implementación, todo funciona como esperaría hasta la última parte del pseudocódigo:

for each triangle in triangulation // done inserting points, now clean up
     if triangle contains a vertex from original super-triangle
        remove triangle from triangulation

Si sigo el pseudocódigo aquí literalmente, puedo terminar con triángulos faltantes en mi triangulación de Delaunay.

Como ejemplo, considere las imágenes a continuación. Los sitios que estoy triangulando se representan como círculos azules. Los triángulos se representan con líneas negras (excluyendo los bordes de la imagen) y conectan sitios o vértices delimitadores / súper triángulos. Los círculos circulares se representan con gris y sus centros se representan con círculos rojos. Las celdas de Voronoi están pintadas con un color diferente para (con suerte) hacer que el problema sea más evidente.

Esta imagen muestra el estado de la triangulación justo antes de realizar los pasos enumerados en el pseudocódigo anterior. Tenga en cuenta que dos de los vértices del súper triángulo están más allá de la derecha y la parte inferior de la imagen.

Esta imagen muestra el paso después de eliminar los triángulos que contienen vértices de súper triángulos sin ninguna otra consideración:

Los tres vértices superiores deben tener un nuevo triángulo con un circuncentro en el punto donde se encuentran las células verdosas / parduzcas. El problema es que el vértice de la esquina que se mostró en la imagen "antes" estaba dentro de este círculo, por lo que el procesamiento regular del algoritmo nunca generó este triángulo.

¿Cómo expreso este caso extremo en pseudocódigo para que pueda verificarlo y resolverlo? Me gustaría evitar algunos bucles horribles de "prueba todas las combinaciones de sitios que comparten un triángulo con un vértice súper triangular para un círculo circunferencial válido".

Leí los documentos de Bowyer y Watson hace un par de años y los volveré a leer para obtener mi respuesta si es necesario. Esperaba que (1) alguien más pudiera tener la respuesta disponible y (2) podría usar Stack Overflow para buscar la respuesta si alguna vez vuelvo a encontrarme con esta pregunta.

Editar

Así que he encontrado una solución relativamente barata pero imperfecta. Mi súper triángulo está determinado programáticamente para rodear el cuadro delimitador de los sitios sin cruzar sus lados. Esta idea fue causada por todo tipo de problemas frustrantes con Java, considerando que algunas de mis coordenadas de circuncentro calculadas o distancias entre coordenadas eran infinitas. Esta precaución me llevó a hacer mi súper triángulo tan pequeño que sus vértices a veces caían en circuncentros válidos de triángulos. El aumento del tamaño del súper triángulo ha hecho que el problema parezca desaparecer. Sin embargo, es posible que un triángulo en el casco convexo pueda ser tan obtuso que uno de los vértices aún pueda caer dentro de un círculo circunferencial válido.

Creo que esto significa que mi pregunta inicial sigue siendo válida frente a las limitaciones de número de coma flotante. ¿Hay alguna forma barata de garantizar que el algoritmo Bowyer-Watson genere una triangulación válida?