Come posso derivare un diagramma di Voronoi dato il suo insieme di punti e la sua triangolazione di Delaunay?
-
01-07-2019 - |
Domanda
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!
Soluzione
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.
Altri suggerimenti
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.
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.
Sono abbastanza sicuro che il "triangolo" http://www.cs.cmu.edu/~quake/triangle.html può generare il voronoi
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?