Come posso derivare un diagramma di Voronoi dato il suo insieme di punti e la sua triangolazione di Delaunay?

Question

Sto lavorando a un gioco in cui creo una mappa casuale di province (a la Risk o Diplomacy).Per creare quella mappa, prima genero una serie di punti semi-casuali, poi immagino le triangolazioni di Delaunay di quei punti.

Fatto ciò, sto ora cercando di creare un diagramma di Voronoi dei punti che funga da punto di partenza per i confini della provincia.I miei dati a questo punto (nessun gioco di parole) consistono nella serie originale di punti e in una raccolta di triangoli di Delaunay.

Ho visto diversi modi per farlo sul web, ma la maggior parte di essi è legata al modo in cui è stato derivato il Delaunay.Mi piacerebbe trovare qualcosa che non abbia bisogno di essere integrato nel Delaunay, ma che possa funzionare solo basandosi sui dati.In caso contrario, sto cercando qualcosa di comprensibile a un principiante della geometria relativa, in contrapposizione alla velocità ottimale.Grazie!

Answer 1

Il diagramma di Voronoi non è altro che il grafico duale della triangolazione di Delaunay.

• Quindi, i bordi del diagramma di Voronoi sono lungo le bisettrici perpendicolari dei bordi della triangolazione di Delaunay, quindi calcola quelle linee.
• Quindi, calcola i vertici del diagramma di Voronoi trovando le intersezioni dei bordi adiacenti.
• Infine, i bordi sono quindi i sottoinsiemi delle linee calcolate che si trovano tra i vertici corrispondenti.

Tieni presente che il codice esatto dipende dalla rappresentazione interna che stai utilizzando per i due diagrammi.

Answer 2

Se la velocità ottimale non è una considerazione, il seguente codice pseudo genererà un diagramma di Voronoi nel modo più duro:

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

Supponendo che tu abbia una classe o struttura "punto", se assegni loro colori casuali, vedrai il familiare schema voronoi quando visualizzi l'output.

Answer 3

Dopo aver provato a utilizzare questo thread come fonte di risposte alla mia domanda simile, ho scoperto che l'algoritmo di Fortune, probabilmente perché è il più popolare e quindi il più documentato, era il più facile da capire.

L'articolo di Wikipedia sull'algoritmo di Fortune mantiene nuovi collegamenti al codice sorgente in C, C# e Javascript.Erano tutti di prim'ordine e portavano bellissimi esempi.

Answer 4

Sono abbastanza sicuro che il "triangolo" http://www.cs.cmu.edu/~quake/triangle.html può generare il voronoi

Answer 5

Ciascuno dei tuoi triangoli di Delaunay contiene un singolo punto del diagramma di Voronoi.

Puoi calcolare questo punto trovando l'intersezione dei tre bisettrici perpendicolari per ogni triangolo.

Il tuo diagramma di Voronoi collegherà questo insieme di punti, ciascuno con i suoi tre vicini più vicini.(ogni vicino condivide un lato del triangolo di Delaunay)

Come pensi di affrontare i casi limite?