Algorithmus zur Berechnung eines Voronoi-Diagramms auf einer Kugel?

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

Frage

Ich suche nach einem einfachen (falls vorhanden) Algorithmus, um das Voronoi-Diagramm für eine Reihe von Punkten auf der Oberfläche einer Kugel zu finden.Quellcode wäre toll.Ich bin ein Delphi-Mann (ja, ich weiß...), aber ich esse auch C-Code.

War es hilfreich?

Lösung

Hier ist ein Papier auf sphärischen Voronoi Diagramme .

Oder wenn Sie Fortran (bleah!) Grok es diese Seite .

Andere Tipps

Update im Juli 2016:

Dank eine Reihe von Freiwilligen (vor allem Nikolai Nowaczyk und I), da für den Umgang mit Voronoi Diagramme auf der Oberfläche einer Kugel in Python jetzt weitaus robuster / korrekter Code ist. Dies ist offiziell als scipy.spatial.SphericalVoronoi ab Version 0.18 von scipy ab. Es gibt ein funktionierendes Beispiel der Nutzung und Plotten in der offiziellen docs .

Der Algorithmus folgt quadratische Zeitkomplexität. Während loglinearen das theoretische Optimum für Voronoi Diagramme auf den Oberflächen von Kugeln ist, ist dies zur Zeit die besten, die wir implementieren konnten zu haben. Wenn Sie möchten, um mehr zu erfahren und helfen bei der Entwicklungsarbeit gibt es einige offene Fragen im Zusammenhang mit der Verbesserung der Art und Weise Python sphärischen Voronoi Diagramme behandelt und die zugehörigen Datenstrukturen:

Für weitere Hintergrundinformationen über die Theorie / Entwicklung / Herausforderungen im Zusammenhang mit diesem Python-Code und damit verbundenen Computational Geometry Anstrengungen, die Sie auch einige Gespräche von Nikolai überprüfen können und I:

Original Antwort:

Ich habe vor kurzem tatsächlich geschrieben einig Open-Source-Python-Code für Voronoi Diagramme auf der Oberfläche einer Kugel: https: / /github.com/tylerjereddy/py_sphere_Voronoi

Die Nutzung, Algorithmus und Einschränkungen auf readthedocs dokumentiert ( http: //py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html ). Es gibt einige detaillierte Beispiele gibt, aber ich werde weiter unten als auch ein oder zwei platzieren. Das Modul übernimmt auch die Berechnung der Voronoi-Bereich Oberflächenbereiche, wenn auch mit einigen numerischen Schwächen in der aktuellen Entwicklungsversion.

Ich habe nicht viele gut dokumentierten Open-Source-Implementierungen für sphärischen Voronoi Diagramme gesehen, aber es hat ein bisschen von Summen über die JavaScript-Implementierung auf Jason Davies' Website ( http://www.jasondavies.com/maps/voronoi/ ). Ich glaube nicht, seinen Code obwohl offen ist. Ich sah auch eine Blog-Post über Python mit einem Teil des Problems ( http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code/ ). Viele der wichtigsten Literaturquellen in den oben zitierten Stellen schien sehr schwierig zu implementieren (ich einige von ihnen versucht), aber vielleicht einige Leute meine Implementierung nützlich oder sogar vorschlagen, Möglichkeiten zur Verbesserung es finden.

Beispiele:

1) Produce ein Voronoi-Diagramm für einen pseudo-zufälligen Satz von Punkten auf der Einheitskugel: 

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)

eingeben Bild Beschreibung hier

2) Berechne die Oberflächenbereiche des Voronoi-Bereich von Polygonen und verifiziert, dass die rekonstituierte Oberfläche ist sinnvoll: 

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

Beachten Sie, dass Delaunay-Triangulation auf einer Kugel nur die konvexe Hülle ist. So können Sie die 3D-konvexe Hülle berechnen (z CGAL verwenden) und die Doppel nehmen.

Es ist ein Papier von INRIA über die Delaunay Triangulation (DT) von Punkten auf einer Kugel liegen: CAROLI , Manuel, et al. Robuste und effiziente Delaunay Triangulation von Punkten auf oder in der Nähe einer Kugel. 2009 , wo sie über eine Implementierung sprechen in CGAL .

Das Papier bezieht sich auf verschiedene verfügbare Implementierung von DT-Algorithmen.

aus dem Papier Zitiert:

  

Eine einfache und Standard-Antwort besteht die 3D-konvexe Hülle bei der Berechnung   die Punkte, die notorisch entsprechen.

zur Berechnung der konvexen Hülle das Papier schlägt vor:

  1. Hull, ein Programm für konvexe Hüllen.
  2. qhull .
  3. Dreidimensionale konvexe Hüllen. in Fortran. dreidimensionale konvexe Hüllen.
  4. STRIPACK in Fortran.

Die DT C ++ Klasse von CGAL hat die Methode dual das Voronoi Diagramm erhalten.

Nach dieser Beitrag von Monique Teillaud (eines des Autor des oben erwähnten Papiers) scheint es mir, im November 2012, dass die Umsetzung noch nicht fertig war.

Es ist schon eine Weile her, seit die Frage beantwortet ist, aber ich habe zwei Papiere gefunden, dass implementieren fortune Algorithmus (Effizienz O (N lg N), Speicher O (N)) über die Oberfläche der Kugel. Vielleicht eine Zukunft Betrachter wird diese Informationen nützlich finden.

Ich arbeite durch sie selbst im Moment, also kann ich es auch nicht erklären. Die Grundidee ist, dass Fortune-Algorithmus auf der Oberfläche der Kugel arbeitet so lange, wie Sie die Punkte Begrenzungs Parabeln korrekt berechnen. Da die Oberfläche der Kugel umschließt, können Sie auch eine kreisförmige Liste verwenden, um die Strandlinie enthalten und keine Sorgen um Zellen am Rande des rechteckigen Raumes Handhabung. Damit können Sie vom Nordpol der Kugel nach Süden kehren und wieder nach oben, auf Websites, Überspringen, dass neue Punkte an den Strand Linie einführen (das Hinzufügen einer Parabel zum Strand Linie) oder die Einführung von Zell Eckpunkten (Entfernen eines Parabel vom Strand Linie).

Beide Papiere erwarten ein hohes Maß an Komfort mit der linearen Algebra, um die Konzepte zu verstehen, und sie halten mich beide an dem Punkt, verlieren sie den Algorithmus selbst anfangen zu erklären. Weder Quellcode bereitstellen, leider.

Ich denke, die Voronoi-Ebene für jeden Punkt konstruiert werden kann, nicht-euklidische Geometrie. Was auf einer 2D-Ebene normalerweise eine Linie war, ist jetzt ein 'großer Kreis' auf der Kugel (siehe Wikipedia: elliptische Geometrie ). Es ist leicht, die Punkte sind auf der falschen Seite eines großen Kreises zwischen zwei Punkten zu finden, die durch einfaches Drehen des Kugel, so dass die Teilung große Kreis der Äquator ist, und dann ist es alle Punkte auf der anderen Hemisphäre als der Punkt, du bist Konstruktion des Voronoi-Ebene für.

Das ist nicht die ganze Antwort, aber das ist, wo ich anfangen würde ..

Es gibt ein schönes Beispielprogramm für ein Voronoi-Diagramm Hier (einschließlich Quellcode für Delphi 5/6).

Ich denke, „Punkte auf der Oberfläche einer Kugel“ bedeutet, dass man sie zunächst auf 2D-Koordinaten umbilden, das Voronoi-Diagramm erstellen und sie dann auf die Koordinaten der Kugeloberfläche umbilden muss.Sind die beiden Formeln aus Wikipedia-Artikel zur UV-Kartierung hier arbeiten?

Beachten Sie auch, dass das Voronoi-Diagramm die falsche Topologie hat (es befindet sich innerhalb eines Rechtecks ​​und „umschließt“ nicht). Hier könnte es hilfreich sein, alle Punkte von (0,0)-(x, y) zum Nachbarn zu kopieren Regionen oberhalb (0, -y * 2)-(x, 0), unterhalb (0, y)-(x, y * 2), links (-x, 0)-(0, y) und rechts (x, 0)-(x*2, y).Ich hoffe, du verstehst, was ich meine, frag ruhig :)

CGAL auf dem „sphärischen Kern“ Paket arbeitet, die genau diese Art von Dingen erlauben würden, zu berechnen, . Leider ist noch nicht freigegeben , aber vielleicht wird es in der nächsten Version sein, da sie bereits erwähnte es in einem google Tech Talk März

von diesem Verwendungszweck: http://www.qhull.org/html/qdelaun.htm

  

die Delaunay-Triangulation von Punkten auf einer Kugel zu berechnen, ihre konvexe Hülle berechnen. Wenn die Kugel die Einheitskugel am Ursprung ist, sind die Facettennormalen die Voronoi Eckpunkte des Eingangs.

Wenn Sie Ihre Punkte innerhalb einer Hemisphäre sind, könnten Sie eine gnomonic Projektion von sphärischem tun Koordinaten auf planare, und dann Triangulierung, da große Kreise gerade werden Linien kürzester Distanz.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top