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

Question

Estoy trabajando en un juego en el que creo un mapa aleatorio de provincias (al estilo Risk o Diplomacy).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 punto (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 cómo se derivó Delaunay.Me encantaría encontrar algo que no necesite integrarse a Delaunay, pero que pueda funcionar basándose únicamente en los datos.De lo contrario, estoy buscando algo comprensible para un novato en geometría relativa, en lugar de una velocidad óptima.¡Gracias!

Answer 1

El diagrama de Voronoi es simplemente la gráfica dual de la triangulación de Delaunay.

• Entonces, las aristas del diagrama de Voronoi están a lo largo de las bisectrices perpendiculares de las aristas de la triangulación de Delaunay, así que calcula esas líneas.
• Luego, calcula los vértices del diagrama de Voronoi encontrando las intersecciones de aristas adyacentes.
• Finalmente, las aristas son los subconjuntos de las líneas que calculaste y 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 2

Si no se considera la velocidad óptima, el siguiente pseudocódigo generará un diagrama de Voronoi de la manera más 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 'puntos', si les asigna colores aleatorios, verá el patrón voronoi familiar cuando muestre la salida.

Answer 3

Después de intentar utilizar este hilo como fuente de respuestas a mi pregunta similar, descubrí 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 hermosos ejemplos.

Answer 4

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

Answer 5

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

Puedes calcular este punto encontrando la intersección de los 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 planea abordar los casos extremos?