Come posso ottenere un dizionario di cellule da questi dati del diagramma Voronoi?

Question

Utilizzando la libreria di generazione del diagramma Voronoi/Delaunay trovata in questo programma, che si basa sull'implementazione originale di Fortune di il suo algoritmo, con un set casuale di punti come dati di input, sono in grado di ottenere i seguenti dati di output:

1. Un elenco dei bordi dal Triangolazione Delaunay, nel senso che per ogni punto di input posso vedere quali punti di input sono i suoi vicini. Non sembrano essere in nessun ordine particolare.
2. Un elenco delle coppie di vertice da Diagramma Voronoi, che posso usare per disegnare il diagramma Voronoi una linea alla volta. Ancora una volta, 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 di un test del mio programma usando 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 sono adeguati se tutto ciò di cui ho bisogno è disegnare i diagrammi Voronoi e Delaunay, non sono informazioni sufficienti per il lavoro reale che sto cercando di fare con questi diagrammi. Ciò di cui ho bisogno è un dizionario di poligoni formati dai vertici di Voronoi, indicizzato dal punto di input in cui ogni poligono è stato formato. Preferibilmente, per ogni poligono, questi punti verrebbero ordinati in senso orario.

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

Quindi in breve, Come posso usare i dati disponibili per me per mettere insieme un dizionario in cui la chiave è uno dei punti di input e i dati indicizzati da quella chiave sono un elenco dei vertici Voronoi che formano il poligono circostante? O in alternativa, queste informazioni sono implicite nei dati che mi sono stati forniti?

Answer 1

L'algoritmo di Fortune è O (n log n) - ma il tuo codice sarà O (n^2), se provi a ricostruire la moda bruto -forza come proposta da Alink.

Il punto di partenza per la mia risposta è che ciò che stai usando per generare le celle non è una libreria, ma piuttosto è solo una classe scritta per concludere ordinatamente il codice originariamente presentato dallo stesso Fortune, e non in realtà una libreria matura. Quindi, l'autore infatti non ha anticipato le tue esigenze e, sebbene le informazioni che desideri siano state calcolate, non sono accessibili.

Internamente, i tuoi punti di input sono archiviati come istanze della struttura "Sito" e l'algoritmo procede a creare mezze bordi, ognuno dei quali mantiene un riferimento a "vertice" che è un puntatore al sito che racchiude. Passando da mezzo bordi naturalmente circumnavigare il sito chiuso - esattamente ciò di cui hai bisogno.

Per accedere a questi dati, ho suggerito di modificare o estendere la classe VoronoidiagramGenerator; Lo farei creando una tabella hash con puntatori del sito come chiave e un solo puntatore a metà come valore. Quindi, modifica il metodo GenerateVoroni, inserendo il tuo nuovo codice immediatamente dopo 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 c'è il tuo dizionario. Quel singolo mezzo bordo ti permetterà di "camminare" il perimetro del poligono che racchiude il sito correlato, che penso sia quello che hai chiesto. Il tuo prossimo problema sarà scoprire in modo efficiente quale Polygon racchiude un nuovo punto dati - ma questa è un'altra domanda :-). Spero che prendi in considerazione la condivisione della tua classe completa - dovrebbe essere significativamente più utile della classe base.

EDIT: ecco un'eccellente presentazione che descrisse tutte sopra nelle immagini: http://ima.udg.es/~sellares/comgeo/vor2d_1.ppt:

• Definizione del diagramma Voronoy
• albero di mezze bordi (vedi foto. Di seguito)
• Algoritmo di Fortunes nelle immagini

Ed ecco un'implementazione C# che potrebbe aiutarti a recuperare il dizionario, come proposto sopra: http://www.codeproject.com/articles/11275/fortune-s-voro-algorithm-implement-in-c

Answer 2

Il tuo elenco di bordi è in qualche modo incompleto, è necessario aggiungere quelli al confine del rettangolo contenente fornito alla chiamata della biblioteca (sembra essere 642.482 qui). Tecnicamente, una suddivisione Voronoi dovrebbe usare alcuni bordi infiniti, ma quelli sono tutti finiti. Presumo 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 non sembrano difficili, solo noiosi. Probabilmente qualcosa come, per ogni lato del rettangolo principale, trova tutti i vertici su di esso (ignorando gli angoli), ordinali (da X per quello orizzontale, per Y per verticale) e dividi quel lato usando questi valori. Ciò genera i bordi mancanti, ma non aggiungerli direttamente alla tua lista principale, perché sono speciali poiché sono gli unici che non separano due celle.

Quindi, per la domanda stessa, andrei così: nel tuo elenco principale di bordi (fornito dalla libreria), ogni bordo separa due celle e se troviamo quali, possiamo semplicemente assegnare quel bordo a ciascuno di questi cellule. Poiché una cella è equivalente a un punto di input, avremo il dizionario desiderato, tranne che con un elenco di bordi anziché vertici, ma è facile da convertire.

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

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

Infine, possiamo convertire ogni elenco di bordi in un elenco di vertici (scaricare ciascuna estremità in un set). Se si desidera risolverli 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 ciascun vertice, calcola il suo angolo da un asse (usa std :: atan2 (x, y)) e utilizzare questo angolo come valore di comparatore per ordinarli (vedi std :: ordinare).

Answer 3

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

Funziona in 2 modalità a) come un utilità triangulate.exe e b) come libreria C per compilarla come utilità devi solo compilare triangolo.c ed eseguire:

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

Per ottenere il diagramma Voronoi (fare riferimento al manuale su Formato) Ho fatto un esperimento con i tuoi dati di input in un file tale.

# <# 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 riporta solo un errore di input dati.

• Lavorare con questo pacchetto direi che spesso non funziona con i dati ïNput che segnalano un errore. Accetta solo poligoni di input (non punti casuali) e il problema qui è che hai un poligono di ingresso autointeratori.
• Non risponde alla tua domanda, segnalando solo un insieme di punti, non un dizionario

Answer 4

Potresti semplicemente usare il triangolo: http://www.cs.cmu.edu/~quake/triangle.html

Answer 5

http://svn.osgeo.org/qgis/trunk/qgis/python/plugins/ftools/tools/voroi.py

Questa implementazione di Python di Carson Farmer ti dà informazioni topologiche