¿Cómo triangular a partir de un diagrama de Voronoï?

Question

Calculé un diagrama de Voronoï a partir de un conjunto de puntos (con Boost.polygon ).

Intento encontrar una triangulación de Delaunay, conectando el centro de cada celda para cada arista de Voronoï, pero se me escapan algunas aristas.

En la siguiente imagen, los puntos rojos son mis puntos iniciales, las líneas azules son las aristas de Voronoï (he ignorado las aristas infinitas), y las líneas verdes son las aristas de triangulación (una arista verde por cada arista azul, conectando dos orígenes de celdas).

Podemos ver que faltan las aristas diagonales. ¿Qué me falta?

Aquí hay más ejemplos:

Answer 1

Cuando un vértice de un diagrama de Voronoi tiene valencia mayor que tres (a veces cuatro en tus ejemplos) los triángulos de Delaunay no son triángulos (cuadriláteros en los ejemplos).

El segundo ejemplo muestra cómo una pequeña perturbación puede convertir un vértice cuatrivalente en dos vértices trivalentes próximos entre sí. Entonces hay un segmento corto que los une que tiene una perpendicular honesta para conectar dos de los puntos originales. En el caso del cuadrilátero, ninguna de las dos diagonales es la correcta.

Si se eligen centros al azar en el plano, todos los vértices tendrán valencia tres con probabilidad 1.

Puede que haya convenciones en las definiciones sobre si las diagonales "perdidas" deben ser consideradas cuando las coincidencias raras ocurren, y su software piensa que no. (No he mirado el software, y la última vez que pensé en los diagramas de Voronoi fue hace años).