geometry - triangulacion - ¿Cómo obtengo un diagrama de Voronoi dado su conjunto de puntos y su triangulación de Delaunay?

triangulacion geometria computacional

Question

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.

Una vez hecho esto, 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 hacer esto en la web, pero la mayoría de ellas 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!

Answer 1

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 una ventaja y tendrás la triangulación delaunay (y viceversa).

Answer 2

Cada uno de tus triángulos de Delaunay contiene un único punto del diagrama de Voronoi.

Puede calcular este punto encontrando la intersección de las tres bisectrices perpendiculares 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 los casos extremos?

Answer 3

Si la velocidad óptima no es una consideración, el siguiente código psuedo generará un diagrama de Voronoi 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

Suponiendo que tiene una clase o estructura de ''punto'', si les asigna colores aleatorios, verá el patrón de voronoi familiar cuando muestre la salida.

Answer 4

Estoy bastante seguro de que ''triángulo'' http://www.cs.cmu.edu/~quake/triangle.html puede generar el voronoi

Answer 5

El diagrama de Voronoi es solo el gráfico dual de la triangulación de Delaunay.

• Entonces, los bordes del diagrama de Voronoi están a lo largo de las bisectrices perpendiculares de los bordes de la triangulación de Delaunay, así que calcule esas líneas.
• Luego, calcula 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 has calculado 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.

Answer 6

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 y por lo tanto el más documentado, era el más fácil de entender.

El artículo de Wikipedia sobre el algoritmo de Fortune mantiene enlaces nuevos al código fuente en C, C # y Javascript. Todos ellos eran de primera categoría y venían con bellos ejemplos.