fest, ob quadratische Zelle innerhalb Polygon

Question

Zum Beispiel möchte ich 14 die Gitterzellen (Quadrate) innerhalb oder teilweise innerhalb Polygon # mit # 14 in Verbindung gebracht werden. Gibt es einen Algorithmus, der berechnet, wenn ein Quadrat innerhalb eines Polygons effizient ist?

Ich habe die Koordinaten der Kanten, die das Polygon bilden.

Answer 1

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:

1. Formular ein Polygon für den Platz.
2. Find its intersection mit allen Zellen.
3. Calculate area dieser Schnittpunkte.
4. 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.