per diagrammi voronoi ponderati?

Question

Qualcuno può indicarmi un'implementazione di riferimento su come costruire un diagramma di voronoi (moltiplicato e/o addizionalmente) ponderato, che è preferibilmente basato sull'algoritmo voronoi di Fortune?

Il mio obiettivo: Dato un insieme di punti (ogni punto ha un peso) e un insieme di bordi di contorno (di solito un rettangolo) Voglio costruire un diagramma di Voronoi ponderata utilizzando Python o il processing.org- struttura. Ecco un example.

Quello che ho lavorato finora: Finora ho implementato l'algoritmo di fortuna così come il "Voronoi tassellazione baricentrico" presentato in Michael Balzer's paper. Algoritmo 3 indica come devono essere regolati i pesi, tuttavia, quando lo implemento, la mia geometria non funziona più. Per risolvere questo problema, l'algoritmo di sweep-line deve essere aggiornato per tener conto dei pesi, ma finora non sono stato in grado di farlo. Quindi mi piacerebbe vedere come le altre persone hanno risolto questo problema.

Answer 1

Per additiva ponderata Voronoi Diagram: Remember that a power diagram in dimension n is only a(n unweighted) Voronoi diagram in dimension n+1.

Per questo, basta ricordare che il diagramma di Voronoi di un set di punti è invariante se si aggiunge una costante alle coordinate e che il diagramma Voronoi ponderato può quindi essere scritto come un diagramma Voronoi non ponderato utilizzando le coordinate, ad esempio in 2D sollevato in 3D:
(x_i, y_i, sqrt (C - w_i))
dove w_i è il peso del seme e C è qualsiasi costante arbitrariamente grande (in pratica, uno appena abbastanza piccolo tale che C- w_i è positivo).
Una volta che il diagramma è stato calcolato, basta eliminare l'ultimo componente.

Quindi, in pratica, è sufficiente trovare una libreria in grado di gestire i diagrammi Voronoi in dimensione n + 1 rispetto al problema. CGAL può farlo. Ciò rende anche l'implementazione estremamente facile.

Answer 2

Se si ha dimestichezza con Octave, è possibile fare riferimento al codice fornito nel loro library.

Answer 3

Questo calcolo non è semplice, ma è disponibile in CGAL. Vedere the manual pages here.

---

---

Vedi anche il progetto Effective Computational Geometry, che impiega e supporta CGAL:

---

                   

Answer 4

C'è poco codice "open source" immediatamente disponibile, nel caso in cui le distanze dai centri siano ponderate con un fattore moltiplicativo. Per quanto ne so, nessuno degli attuali pacchetti CGAL copre questo caso.

sito splendidamente colorate di Takashi Ohyama fornisce implementazioni Java http://www.nirarebakun.com/voro/emwvoro.html fino a 100 punti con un semplice algoritmo (euclidee e Manhattan distanze). C'è anche un documento che descrive questo semplice algoritmo di intersezione e un'implementazione approssimativa entro il tempo O (n^3), come plugin per TerraView. Tuttavia, non riesco a trovare la fonte di questo plugin nel repository TerraView/TerraLib: http://www.geoinfo.info/geoinfo2011/papers/mauricio1.pdf

Aurenhammer e Edelsbrunner descrivono un algoritmo ottimale n^2 tempo, ma io sono a conoscenza di codice a disposizione di questo.