Algoritmo per il calcolo di un diagramma di Voronoi su una sfera?

StackOverflow https://stackoverflow.com/questions/545870

Domanda

Sto cercando un algoritmo semplice (se esiste) per trovare il diagramma di Voronoi per un insieme di punti sulla superficie di una sfera. Il codice sorgente sarebbe grande. Sono un uomo di Delphi (sì, lo so ...), ma mangio C-codice troppo.

È stato utile?

Soluzione

Ecco una carta su sferica Voronoi diagrammi .

O se Grok Fortran (bleah!) C'è questo sito .

Altri suggerimenti

Aggiornamento nel mese di luglio 2016:

Grazie ad un numero di volontari (in particolare Nikolai Nowaczyk e I), ora c'è molto più robusto / codice corretto per la movimentazione di diagrammi di Voronoi sulla superficie di una sfera in Python. Questo è ufficialmente disponibile come scipy.spatial.SphericalVoronoi dalla versione 0.18 di SciPy in poi. C'è un esempio di lavoro di utilizzo e tramando nella docs .

L'algoritmo segue quadratica tempo la complessità. Mentre loglineari è il limite teorico di diagrammi di Voronoi sulle superfici delle sfere, questo è attualmente il migliore siamo stati in grado di attuare. Se desideri saperne di più e aiutare con lo sforzo di sviluppo ci sono alcuni problemi aperti legati al miglioramento della strada Python gestisce diagrammi di Voronoi sferiche e le relative strutture di dati:

Per ulteriori sfondo sulla teoria / sviluppo / sfide relativi a questo codice Python e dei relativi sforzi geometria computazionale si può anche verificare alcune colloqui di Nikolai e io:

Risposta originale:

In realtà ho recentemente scritto un po 'di codice Python open source per diagrammi di Voronoi sulla superficie di una sfera: https: / /github.com/tylerjereddy/py_sphere_Voronoi

L'utilizzo, algoritmo, e le limitazioni sono documentate su readthedocs ( http: //py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html ). Ci sono alcuni esempi dettagliati lì, ma metterò uno o due al di sotto pure. Il modulo gestisce anche il calcolo delle superfici regione di Voronoi, anche se con alcune debolezze numerici nella versione di sviluppo attuale.

Non ho visto molte implementazioni open source ben documentati per diagrammi di Voronoi sferiche, ma c'è stato un po 'di buzz circa l'implementazione JavaScript sul sito Jason Davies' ( http://www.jasondavies.com/maps/voronoi/ ). Non credo che il suo codice è aperto però. Ho visto anche un post su come utilizzare Python a che fare con una parte del problema ( http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code/ ). Molte delle fonti bibliografiche primarie citati nei messaggi di cui sopra sembrava molto difficile da implementare (ho provato alcuni di loro), ma forse alcune persone a trovare la mia implementazione utile o anche suggerire modi per migliorarla.

Esempi:

1) Produrre un diagramma di Voronoi per un insieme pseudo-casuale di punti sulla sfera unitaria: 

import matplotlib
import matplotlib.pyplot as plt
import matplotlib.colors as colors
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
import numpy as np
import scipy as sp
import voronoi_utility
#pin down the pseudo random number generator (prng) object to avoid certain pathological generator sets
prng = np.random.RandomState(117) #otherwise, would need to filter the random data to ensure Voronoi diagram is possible
#produce 1000 random points on the unit sphere using the above seed
random_coordinate_array = voronoi_utility.generate_random_array_spherical_generators(1000,1.0,prng)
#produce the Voronoi diagram data
voronoi_instance = voronoi_utility.Voronoi_Sphere_Surface(random_coordinate_array,1.0)
dictionary_voronoi_polygon_vertices = voronoi_instance.voronoi_region_vertices_spherical_surface()
#plot the Voronoi diagram
fig = plt.figure()
fig.set_size_inches(2,2)
ax = fig.add_subplot(111, projection='3d')
for generator_index, voronoi_region in dictionary_voronoi_polygon_vertices.iteritems():
   random_color = colors.rgb2hex(sp.rand(3))
   #fill in the Voronoi region (polygon) that contains the generator:
   polygon = Poly3DCollection([voronoi_region],alpha=1.0)
   polygon.set_color(random_color)
   ax.add_collection3d(polygon)
ax.set_xlim(-1,1);ax.set_ylim(-1,1);ax.set_zlim(-1,1);
ax.set_xticks([-1,1]);ax.set_yticks([-1,1]);ax.set_zticks([-1,1]); 
plt.tick_params(axis='both', which='major', labelsize=6)

entrare descrizione dell'immagine qui

2) Calcola le superfici dei poligoni regione Voronoi e verificare che la superficie ricostituito è sensibile: 

import math
dictionary_voronoi_polygon_surface_areas = voronoi_instance.voronoi_region_surface_areas_spherical_surface()
theoretical_surface_area_unit_sphere = 4 * math.pi
reconstituted_surface_area_Voronoi_regions = sum(dictionary_voronoi_polygon_surface_areas.itervalues())
percent_area_recovery = round((reconstituted_surface_area_Voronoi_regions / theoretical_surface_area_unit_sphere) * 100., 5)
print percent_area_recovery
97.87551 #that seems reasonable for now

Si noti che la triangolazione Delaunay su una sfera è solo il guscio convesso. Così si può calcolare il convesso 3D (per esempio usando CGAL) e prendere la superstrada.

V'è una carta da INRIA sulla Delaunay Triangolazione (DT) di punti che si trovano su una sfera: CAROLI , Manuel, et al. triangolazioni Delaunay ciente robuste ed ef fi di punti su o vicino ad una sfera. 2009. dove si parla di un'implementazione in CGAL .

Il documento si riferisce a vari implementazione di algoritmi disponibili DT.

Citando dalla carta:

  

Una risposta semplice e standard consiste nel calcolare l'inviluppo convesso 3D   dei punti, che è notoriamente equivalente.

per il calcolo convesso la carta suggerisce:

  1. Hull, un programma per scafi convessa.
  2. Qhull .
  3. scafi convessi tridimensionali. in FORTRAN. tRIDIMENSIONALE scafi convessa.
  4. STRIPACK in FORTRAN.

La classe DT C ++ del CGAL ha il metodo di dual per ottenere il diagramma di Voronoi.

questo post da Monique Teillaud (uno degli autori del documento di cui sopra) mi sembra che a novembre 2012 l'attuazione non era ancora pronto.

E 'stato un po' che la questione è stata risolta, ma ho trovato due carte che implementare algoritmo di Fortune (efficienza O (N lg N), memoria O (N)) sulla superficie della sfera. Forse un futuro spettatore trovare queste informazioni utili.

Sto lavorando attraverso di loro me stesso in questo momento, quindi non posso spiegarlo bene. L'idea di base è che l'algoritmo di fortuna lavora sulla superficie della sfera fino a quando si calcola correttamente i punti parabole di delimitazione. Poiché la superficie della sfera avvolge, è anche possibile utilizzare una lista circolare per contenere la linea della spiaggia e non preoccuparsi di gestire le cellule ai margini dello spazio rettangolare. Con questo, si può spazzare dal polo nord della sfera a sud e il backup di nuovo, saltando a siti che introducono nuovi punti alla linea di mare (l'aggiunta di una parabola alla linea di spiaggia) o l'introduzione dei vertici delle celle (la rimozione di un parabola dalla linea di spiaggia).

Entrambi i giornali si aspettano un elevato livello di comfort con l'algebra lineare per capire i concetti, ed entrambi mi tengono perdere nel punto cominciano spiegare lo stesso algoritmo. Né fornire il codice sorgente, purtroppo.

Credo piano Voronoi per ciascun punto può essere costruito utilizzando geometria non-euclidea. Quello che era normalmente una linea su un piano 2D, ora è un 'grande cerchio' sulla sfera (vedi Wikipedia: ellittica geometria ). E 'facile da trovare quale i punti sono sul lato sbagliato di ogni grande cerchio tra due punti, semplicemente ruotando la sfera in modo che il grande cerchio che divide è l'equatore, e poi è tutti i punti della emisfero rispetto al punto sei la costruzione del piano di Voronoi per.

Questa non è la risposta intera, ma questo è dove mi piacerebbe iniziare ..

C'è un bel programma di esempio diagramma di Voronoi qui (incluso il codice sorgente per Delphi 5/6).

Credo che "punti sulla superficie di una sfera" significa che è necessario prima di loro rimappare a 2D coordinate, creare il diagramma di Voronoi e poi li rimappare a sfera coordinate superficiali. Sono le due formule da Wikipedia UV articolo mappatura lavorare qui?

Si noti inoltre che il diagramma di Voronoi avrà la topologia sbagliato (è all'interno di un rettangolo e non "wrap around"), qui si potrebbe contribuire a copiare tutti i punti da (0,0) - (x, y) alle regioni confinanti sopra (0, y * 2) - (x, 0), seguito (0, y) - (x, y * 2), a sinistra (-x, 0) - (0, y) e destra (x, 0) - (x * 2, y). Spero che tu sai cosa voglio dire, non esitate a chiedere:)

CGAL sta lavorando sul pacchetto "sferica kernel", che consentirebbe di calcolare esattamente questo genere di cose . Purtroppo, non è ancora rilasciato , ma forse sarà nella loro prossima release, dal momento che già menzionato in un discorso tecnologia google marzo

Citando da questo riferimento: http://www.qhull.org/html/qdelaun.htm

  

Per calcolare la triangolazione Delaunay di punti su una sfera, calcolare la loro convesso. Se la sfera è la sfera unitaria all'origine, le normali sfaccettatura sono i vertici Voronoi dell'ingresso.

Se i punti sono all'interno di un emisfero, si potrebbe fare una proiezione gnomonica da sferiche a planare coordinate, e poi triangolare, dal momento che i grandi-cerchi diventano linee rette di distanza più breve.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top