Wenn ich es richtig machen, dann ist dies eine Implementierung von Fortune's algorithm in JavaScript, die einen Satz von 2-D-Punkten nimmt (so genannten sites
) und gibt eine Struktur für ein Voronoi diagram enthält Daten für diese Punkte berechnet. Es gibt Polygone in einer Liste namens cells
zurück. Es scheint Euclidean distance als Messung zu verwenden. Wenn es wahr ist, wissen wir, dass Polygone immer konvex sind (siehe Formale Definition Abschnitt in Voronoi wiki page). Jetzt
, sind diese Optionen, dieses Problem zu lösen (schwer zu einfach):
1. Polygon Clipping:
- Formular ein Polygon für den Platz.
- Find its intersection mit allen Zellen.
- Calculate area dieser Schnittpunkte.
- Finden Sie die größte Kreuzung.
2- Punkt in Polygon:
Sie können auch einfach die Zelle finden, die Mitte des Platzes im Inneren liegt. Ray casting ist ein robuster PIP-Algorithmus. Es gibt zwar einen einfacheren Ansatz für konvexe Polygone (siehe Abschnitt Konvexe Polygone here).
3. Abstand zwischen den Punkten:
ich, wenn Sie wissen, dass die site
zu jedem cell
assoziiert dann müssen Sie nur Abstand zwischen Zentrum Platz für alle sites
zu berechnen. Unabhängig davon, was distance measurement Sie verwenden, um die Voronoi zu berechnen, liegt der Mittelpunkt des Quadrats innerhalb der cell
, die Entfernung von ihm ist site
ist minimal, da dies tatsächlich die Idee für die Partitionierung der Ebene in einem Voronoi-Diagramm ist.
Ausnahmen:
- Erster Ansatz rechnerisch teuer ist, aber am genauesten. Zweite und dritte Optionen funktionieren in den meisten Fällen in Ordnung, aber es gibt Ausnahmen, die sie nicht richtig entscheiden:
recht sind sehr ähnlich
- zweite und dritte, aber die Kehrseite von PIP ist Fälle, in denen der Punkt auf Kanten des Polygons liegt, die mehr Aufwand für die Erkennung kosten.
Was ist über das Polygon bekannt, wenn überhaupt? Ist es immer konvex? Oder kann es willkürlich sein? (Eine Voronoi-Zelle durch Zufall?) – AnT
Ja, es ist eine Voronoi-Zelle. –
Ist das Voronoi das Ergebnis des Clustering-Prozesses? Genauer gesagt, haben Sie Koordinaten von Clusterzentren und eine Ähnlichkeitsmessung? – saastn