Estoy trabajando en un juego donde creo un mapa aleatorio de provincias (a la Riesgo o Diplomacia). Para crear ese mapa, primero genero una serie de puntos semialeatorios y luego calculo las triangulaciones de Delaunay de esos puntos.¿Cómo obtengo un diagrama de Voronoi dado su conjunto de puntos y su triangulación de Delaunay?
Con eso hecho, ahora estoy buscando crear un diagrama de Voronoi de los puntos que sirva como punto de partida para las fronteras de la provincia. Mis datos en este momento (sin juego de palabras) consisten en la serie original de puntos y una colección de triángulos de Delaunay.
He visto varias formas de hacerlo en la web, pero la mayoría están relacionadas con la forma en que se derivó Delaunay. Me encantaría encontrar algo que no necesite ser integrado a Delaunay, pero puede funcionar solo con los datos. En su defecto, estoy buscando algo comprensible para un novato de geometría relativa, a diferencia de la velocidad óptima. ¡Gracias!
También puede encontrar el diagrama dual (es decir, Voronoi) simplemente calculando las circunferencias de todos los triángulos y conectando dos circunferencias cuyos triángulos comparten un borde. – batty
Como se sugiere en el comentario anterior, lo haría en dos pasos: 1. Calcule el circuncentro de cada triángulo de Delaunay -> estos son los vértices de Voronoi. Consulte http://en.wikipedia.org/wiki/Circumscribed_circle#Circumscribed_circles_of_triangles 2. Para cada borde de Delaunay, calcule un borde Voronoi: el segmento que conecta los circuncentros de los dos triángulos vecinos de Delaunay. –
@ balint.miklos ¿Qué hacer con sitios externos/triángulos? – Orient