2008-09-17 17 views
23

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!

Respuesta

18

El diagrama de Voronoi es sólo el doble gráfica de la triangulación de Delaunay.

  • Así, los bordes del diagrama Voronoi son a lo largo de las bisectrices perpendiculares de los bordes de la triangulación de Delaunay, así calcular esas líneas.
  • Luego, calcule los vértices del diagrama de Voronoi encontrando las intersecciones de los bordes adyacentes.
  • Finalmente, los bordes son los subconjuntos de las líneas que se calcularon que se encuentran entre los vértices correspondientes.

Tenga en cuenta que el código exacto depende de la representación interna que está utilizando para los dos diagramas.

+17

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

+5

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. –

+2

@ balint.miklos ¿Qué hacer con sitios externos/triángulos? – Orient

0

Bueno, la razón por la cual las cosas están unidas es porque la triangulación de Delaunay y el diagrama de Voronoi son estructuras duales. Lo que significa que es pan comido ir de voronoi a delaunay y viceversa.

Lo que significa que si tienes un diagrama voronoi, todo lo que tienes que hacer es conectar los puntos que comparten un borde y tendrás la triangulación delaunay (y viceversa).

+2

Si solo conecta (es decir, agrega un borde entre) los puntos que comparten una ventaja, obtiene el gráfico original, ¿eh? –

8

Si la velocidad óptima no es una consideración, el siguiente pseudo código generará un Voronoi diagrama de la manera difícil:

for yloop = 0 to height-1 
    for xloop = 0 to width-1 

    // Generate maximal value 
    closest_distance = width * height 

    for point = 0 to number_of_points-1 
     // calls function to calc distance 
     point_distance = distance(point, xloop, yloop) 

     if point_distance < closest_distance 
     closest_point = point 
     end if 
    next 

    // place result in array of point types 
    points[xloop, yloop] = point 

    next 
next 

Asumiendo que tiene una clase de 'punto' o estructura, si se les asigna los colores al azar, luego verá el patrón familiar de voronoi cuando muestre la salida.

+0

Eso es muy lindo y elegante, pero no veo ningún uso para un diagrama de Voronoi generado como una imagen. Tal vez hay uno? – Tara

+1

No como una imagen per se, pero la he usado para la generación mundial basada en mosaico procedural (donde cada tesela está determinada por la celda a la que pertenece). – Garan

0

Cada uno de sus triángulos de Delaunay contiene un solo punto del diagrama de Voronoi.

Puede calcular este punto encontrando la intersección de los tres perpendicular bisectors para cada triángulo.

Su diagrama de Voronoi conectará este conjunto de puntos, cada uno con sus tres vecinos más cercanos. (cada vecino comparte un lado del triángulo de Delaunay)

¿Cómo planeas acercarte a las cajas de borde?

+0

Tenga en cuenta que, aunque para cada triángulo de Delaunay corresponde un vértice de Voronoi, este vértice ** también puede estar fuera del triángulo **. vea un ejemplo aquí: http://www.mathopenref.com/trianglecircumcenter.html –

2

Después de tratar de usar este hilo como fuente de respuestas a mi propia pregunta similar, encontré que el algoritmo de Fortune -probablemente porque es el más popular &, el más documentado- era el más fácil de entender.

The Wikipedia article on Fortune's algorithm mantiene enlaces recientes al código fuente en C, C# y Javascript. Todos ellos eran de primera categoría y venían con bellos ejemplos.

Cuestiones relacionadas