Come posso ottenere un dizionario di celle da questi dati di Voronoi Diagram?

Question

Utilizzando la libreria schema di generazione voronoi/delaunay trovato in this program, che si basa su implementazione originale Fortune di his algorithm, con un insieme casuale di punti come dati in ingresso, sono in grado di ottenere i seguenti dati d'uscita:

1. Un elenco dei bordi dello Delaunay Triangulation, il che significa che per ogni punto di ingresso, posso vedere quali punti di input sono i suoi vicini. Non sembrano essere in un ordine particolare.
2. Un elenco delle coppie di vertici da Voronoi Diagram, che posso utilizzare per disegnare il diagramma di Voronoi una riga alla volta. Di nuovo, apparentemente in nessun ordine particolare.
3. Un elenco senza nome di coppie di punti, che sembra essere solo la stessa lista di 2, ma in un ordine diverso.
4. Un elenco dei vertici formati nel diagramma Voronoi, anche apparentemente in nessun ordine particolare.

Ecco un esempio di dati da un test del mio programma che usano questa libreria:

Input points: 
0 (426.484, 175.16) 
1 (282.004, 231.388) 
2 (487.891, 353.996) 
3 (50.8574, 5.02996) 
4 (602.252, 288.418) 

Vertex Pairs: 
0 (387.425, 288.533) (277.142, 5.15565) 
1 (387.425, 288.533) (503.484, 248.682) 
2 (277.142, 5.15565) (0, 288.161) 
3 (387.425, 288.533) (272.213, 482) 
4 (503.484, 248.682) (637.275, 482) 
5 (503.484, 248.682) (642, 33.7153) 
6 (277.142, 5.15565) (279.477, 0) 

Voronoi lines?: 
0 (279.477, 0) (277.142, 5.15565) 
1 (642, 33.7153) (503.484, 248.682) 
2 (503.484, 248.682) (637.275, 482) 
3 (387.425, 288.533) (272.213, 482) 
4 (277.142, 5.15565) (0, 288.161) 
5 (387.425, 288.533) (503.484, 248.682) 
6 (277.142, 5.15565) (387.425, 288.533) 

Delaunay Edges: 
0 (282.004, 231.388) (487.891, 353.996) 
1 (602.252, 288.418) (487.891, 353.996) 
2 (426.484, 175.16) (487.891, 353.996) 
3 (426.484, 175.16) (602.252, 288.418) 
4 (50.8574, 5.02996) (282.004, 231.388) 
5 (426.484, 175.16) (282.004, 231.388) 
6 (50.8574, 5.02996) (426.484, 175.16) 

Vertices: 
0 (277.142, 5.15565) 
1 (503.484, 248.682) 
2 (387.425, 288.533) 
3 (0, 288.161) 
4 (272.213, 482) 
5 (637.275, 482) 
6 (642, 33.7153) 
7 (279.477, 0) 

Mentre i dati di cui sopra è adeguata se ho solo bisogno di disegnare i diagrammi di Voronoi e Delaunay, è non sono abbastanza informazioni per il lavoro reale che sto cercando di fare con questi diagrammi. Quello di cui ho bisogno è un dizionario di poligoni formato dai vertici di Voronoi, indicizzato dal punto di ingresso in cui è stato formato ogni poligono. Preferibilmente, per ogni poligono, questi punti dovrebbero essere ordinati in senso orario.

Con le informazioni di cui sopra, potrei assegnare implicitamente dati a ciascuna regione, assegnare i dati agli angoli se necessario, dire quali regioni condividono i bordi (usando i bordi di Delaunay) e fare un'analisi di conseguenza.

Quindi, in breve, , come posso utilizzare i dati disponibili per mettere insieme un dizionario in cui la chiave è uno dei punti di input, ei dati indicizzati da quella chiave sono una lista dei vertici di Voronoi che si formano il poligono circostante? O in alternativa, quell'informazione è da qualche parte implicita nei dati che ho ricevuto?

Answer 1

L'algoritmo di Fortune è O (n log n) - ma il codice sarà O (n^2), se si tenta di ricostruire le celle in modalità brute-force come proposto da Alink.

Il punto di partenza per la mia risposta è che ciò che si sta utilizzando per generare le celle non è una libreria, ma piuttosto è solo a class written to neatly wrap up the code originally presented by Fortune himself e non in realtà una libreria matura. Quindi, l'autore in effetti non ha previsto le tue esigenze e, sebbene le informazioni che desideri siano state calcolate, non sono accessibili.

Internamente, i punti di ingresso vengono memorizzati come istanze della struct "Sito", e l'algoritmo procede per creare half-edges, ognuno dei quali mantiene un "vertice" di riferimento , che è un puntatore al sito che racchiude. Camminando lungo i semitoni, circumnavigate naturalmente il Sito racchiuso, esattamente ciò di cui avete bisogno.

Per accedere a questi dati, ho suggerito di modificare o estendere la classe VoronoiDiagramGenerator; Lo farei creando una tabella hash con puntatori Site come chiave e un singolo puntatore HalfEdge come valore. Quindi, modificare il metodo generateVoroni, inserendo il nuovo codice che segue immediatamente la chiamata a Voronoi:

For each HalfEdge in ELHash 
     Get table entry for current half edge's Site 
     If site in table has null HalfEdge reference 
      set current HalfEdge reference 
     End If 
End For each 

... e non v'è il dizionario. Quel singolo mezzo bordo ti permetterà di "percorrere" il perimetro del poligono che racchiude il sito correlato, che credo sia quello che hai chiesto. Il tuo prossimo problema sarà scoprire in modo efficiente il che il poligono racchiude qualche nuovo punto dati, ma questa è un'altra domanda :-). Spero che tu prenda in considerazione la condivisione della tua classe completata - dovrebbe essere molto più utile della classe base.

Edit: Ecco una presentazione eccellente descibing tutto detto sopra in immagini: http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt:

• definizione di Voronoy Diagramma
• albero di mezze bordi (vedi foto.sotto) Algoritmo
• fortune in immagini

E qui è un'implementazione C#, che potrebbe aiutare a recuperare il dizionario, come proposto in precedenza: http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

Answer 2

si potrebbe utilizzare Triangolo: http://www.cs.cmu.edu/~quake/triangle.html

Answer 3

Il tuo elenco dei bordi è in qualche modo incompleto, è necessario aggiungere quelli al confine del rettangolo che contiene fornito alla chiamata di libreria (sembra essere 642.482 qui). Tecnicamente, una suddivisione Voronoi dovrebbe usare alcuni bordi infiniti, ma quelli sono tutti finiti. Suppongo che tu voglia anche questi poligoni "aperti" vicino a questo confine, dal momento che sono tutti così nel tuo esempio.

L'aggiunta di quei bordi del bordo non sembra difficile, solo noiosa. Probabilmente qualcosa di simile, per ogni lato del rettangolo principale, trova tutti i vertici su di esso (ignorando gli angoli), ordinali (da x per quello orizzontale, da y per verticale) e suddividi quel lato usando questi valori. Ciò genera i bordi mancanti, ma non li aggiunge direttamente all'elenco principale, perché sono speciali poiché sono gli unici a non separare due celle.

Quindi, per la domanda in sé, vorrei fare così: Nell'elenco principale dei bordi (fornito dalla libreria), ogni spigolo separa due celle e se troviamo quali, quindi possiamo semplicemente assegnare quel bordo a ciascuna di queste cellule. Dato che una cella è equivalente a un punto di input, avremo il dizionario desiderato, tranne che con un elenco di spigoli anziché di vertici, ma è facile convertirlo.

Ora per ottenere queste 2 celle: Calcolare il punto medio del bordo e da questo, trovare i due punti di ingresso più vicini semplicemente ripetendo l'elenco mantenendo le 2 distanze più piccole. Per le proprietà della struttura di Voronoi, questi due sono quelli che formano le due celle. Si noti che queste due distanze dovrebbero essere uguali, ma l'imprecisione del galleggiante probabilmente introdurrà una leggera differenza.

Per finire, aggiungi i bordi del bordo che abbiamo generato lungo il rettangolo principale, ma per quelli, basta usare il primo punto di input più vicino, poiché sono solo adiacenti a una cella.

Infine, possiamo convertire ciascun elenco di spigoli in un elenco di vertici (eseguire il dump di ciascun punto finale in un set). Se vuoi ordinarli in senso orario, nota che è un poligono convesso con un punto di input all'interno. Quindi, puoi semplicemente generare il vettore che va dal punto di input a ogni vertice, calcola il suo angolo da un asse (usa std :: atan2 (x, y)) e usa questo angolo come valore di confronto per ordinarli (vedi std :: ordinare).

Answer 4

Ho usato il pacchetto Triangolo per generare la triangolazione di Dalaunay: http://www.cs.cmu.edu/~quake/triangle.html

Funziona in 2 modi a) come un programma di utilità triangulate.exe e b) come una libreria C Per compilare come un programma di utilità è sufficiente compilare ed eseguire triangle.c:

triangulate -vZ input.poly 
    #v -voronoy, Z - starting from 0 index 

a ottenere diagramma di Voronoi (Consultare il manuale su .poly format) ho fatto un esperimento con i tuoi dati di input in un file di tale .poly:

# <# of vertices> <dimension (must be 2)> <# of attributes> <# of boundary markers (0 or 1)> 
5 2 0 0 
# Following lines: <vertex #> <x> <y> [attributes] [boundary marker] 
0 426.484 175.16 
1 282.004 231.388 
2 487.891 353.996 
3 50.8574 5.02996 
4 602.252 288.418 
#One line: <# of segments> <# of boundary markers (0 or 1)> 
5 0 
#Following lines: <segment #> <endpoint> <endpoint> [boundary marker] 
0 0 1 
1 1 2 
2 2 3 
3 3 4 
4 4 0 

Ma esso segnala solo errore nei dati di input.

• Lavorando con questo pacchetto, direi che spesso non funziona con i dati ïnput che riportano un errore. Accetta solo poligoni di input (non punti casuali) e il problema è che si dispone di poligono di input autointersecante.
• Non rispondere alla tua domanda, riportando solo insieme di punti, non un dizionario

Answer 5

http://svn.osgeo.org/qgis/trunk/qgis/python/plugins/fTools/tools/voronoi.py

Questa implementazione di pitone da Carson Farmer vi dà informazioni topologiche