Wie kann ich testen, ob Punkte innerhalb eines Polygons liegen?

Ich habe 2D-Punkte, deren Grenzen ein Polygon darstellen. Die Punkte befinden sich an ganzzahligen Positionen (keine Brüche möglich).

Jetzt möchte ich einen Enumerator in C # erstellen, der alle Punkte innerhalb des Polygons zurückgibt . Die Implementierung des Enumerators ist nicht das Problem, aber wie bekomme ich alle Punkte effizient? Das Polygon kann ziemlich groß sein.

Was Sie suchen, ist eine Lösung für das Problem "Punkt im Polygon". Es wird in Wikipedia hier beschrieben :

Sie finden C-Code über die Links zu Computational Geometry in C oder an vielen anderen Stellen, die durch die Suche nach "Point-in-Polygon" -Code gefunden wurden.

Sie müssen alle Punkte mindestens einmal verarbeiten. Wenn diese Prüfung nur einmal durchgeführt wird, können Sie nicht viel tun, um den Test zu beschleunigen, außer ihn durch Parallelität brutal zu erzwingen.

Wenn der Test mehrmals ausgeführt werden soll, gibt es Möglichkeiten, Tabellen vorab zu berechnen, um zu helfen, z. B. ein Raster von Zellen, die als [definitiv innen ( grün im Bild), außen ( rot ) und möglicherweise ( blau )] gekennzeichnet sind. Nur Punkte, die in die blauen Zellen fallen, müssen gegen das Polygon getestet werden.

Wenn es jedoch nur einmal mit nur wenigen Punkten relativ zum Raster oder zu vielen "Vielleicht" -Zellen ausgeführt wird, dauert das Erstellen dieser Tabelle wahrscheinlich länger als nur das Brute-Force-Testen Ihrer Punkte.

Sie müssen viel mehr Punkte als Zellen haben (Raster mit niedriger Auflösung), um einen "Gewinn" zu erzielen, und die meisten Zellen müssen innen oder außen als eindeutig enden (Raster mit hoher Auflösung), um ein Gleichgewicht zu finden, das die Dinge zwischen diesen beschleunigt Zwei Faktoren können schwierig sein.

Es ist einfacher und konsistenter in Bezug auf Gewinne, einfach die Anzahl der Punkte auf mehrere Threads aufzuteilen und einen einfachen Schnittpunkttest mit ungeraden und geraden Werten durchzuführen. GPGPU-Verarbeitung wie OpenCL kann Ihnen diese Art von Test einfach und enorm beschleunigen, indem Sie einfach eine große Anzahl von Kernen verwenden.

Um zu erkennen, dass der Wetterpunkt A über oder unter der Linie L liegt, müssen Sie die Linie L in die Funktion f (x) = y = ax + b verwandeln, indem Sie die beiden Punkte, die die Linie darstellen, als x = P1.xy = P1.y und x = P2 verwenden .xx = P2.x einschließlich dieser in das System. Sobald Sie die Funktion f (x) berechnet haben, müssen Sie einfach testen, ob f (Ax)> <= Ay. Wenn f (Ax)> Ay ist, dann liegt die Linie L über Punkt A. Wenn = 0, dann ist sie auf der Linie, sonst ist sie darunter. Es mag etwas kompliziert aussehen, aber die meisten dieser Berechnungen erfolgen sofort und können nur einmal berechnet werden. Während Sie V-, L- und P-Arrays in der durch das Polygon dargestellten Klasse speichern. y dann ist die Linie L über Punkt A. Wenn = 0, dann ist sie auf der Linie, sonst ist sie darunter. Es mag etwas kompliziert aussehen, aber die meisten dieser Berechnungen sind augenblicklich und können nur einmal berechnet werden. Während Sie V-, L- und P-Arrays in der durch das Polygon dargestellten Klasse speichern. y dann ist die Linie L über Punkt A. Wenn = 0, dann ist sie auf der Linie, sonst ist sie darunter. Es mag etwas kompliziert aussehen, aber die meisten dieser Berechnungen sind augenblicklich und können nur einmal berechnet werden. Während Sie V-, L- und P-Arrays in der durch das Polygon dargestellten Klasse speichern.

PS: Wenn die Linie L mit den Punkten P1 und P2 so ist, dass P1.x = P2.x ist, können Sie keine Funktion basierend auf f (x) = ax + b erstellen. Sie müssen einfach überprüfen, ob der Punkt A (den Sie vergleichen, wenn seine unter oder über der Linie L) A.xP1x. Es ist oben. Wenn Ax = P1.x, dann ist es drauf

Sie könnten es möglicherweise als Graph-Traversal-Problem behandeln. Wenn Sie benachbarte Punkte als "Kinder" voneinander behandeln und jedes Kind Ihrer Grenzpunkte zu einer Liste offener Knoten (dh nicht besuchter Knoten) hinzufügen, kann Ihr Enumerator diese Liste untersuchen.

Falls Sie mit Suchalgorithmen nicht vertraut sind, sieht dies wahrscheinlich folgendermaßen aus:
Für jeden Punkt; Fügen Sie den Punkt zu einer Reihe geschlossener Knoten hinzu (dh besucht). Wenn sich der Punkt innerhalb des Polygons befindet, fügen Sie ihn Ihrem Enumerator hinzu und fügen Sie seine untergeordneten Elemente zu Ihrer Liste offener Knoten hinzu. Fahren Sie fort, bis Ihre Liste der offenen Knoten leer ist. Fügen Sie Ihrer geöffneten Liste auch nur Knoten hinzu, wenn diese noch nicht in Ihrer geschlossenen Liste enthalten sind.

Ein paar Anmerkungen:

• Ich würde argumentieren, dass dieser Ansatz könnte effizienter sein , als einfach Linien durch Ihre Formen zu ziehen. Vor allem; Wenn eines Ihrer Polygone konkav ist, werden beim Zeichnen von Linien möglicherweise einige Abschnitte der Form nicht erkannt, ohne dass eine beliebig große Anzahl von Punkten überprüft werden muss, die nicht innerhalb der Form liegen. Sie haben jedoch einen viel größeren Speicheraufwand als die Verwendung von Leitungen.
• Wenn Sie nicht jeden Punkt sofort benötigen, können Sie mit diesem Ansatz den nächsten Punkt bei Bedarf generieren.
• Sie können die Leistung der Durchquerung verbessern, wenn Ihr Problem durch die Verwendung einer Heuristik gütlich ist. Dies ist am relevantesten, wenn Sie nach einem bestimmten Punkt (oder einer Gruppe von Punkten) suchen, die eine bestimmte Eigenschaft erfüllen.

Guck dir das an. Es funktioniert durch einige sehr klare Diagramme.

http://www.mathopenref.com/coordpolygonarea2.html

Sie berechnen nur die Fläche und Sie zählen Punkte auf. Sie können diese Ideen jedoch anpassen. Schauen Sie sich 'Ein komplexerer Fall' genau an und wie die horizontalen Linien das Polygon in eine Reihe von Trapezoiden unterteilen (wenn Sie ein Dreieck als entartetes Trapez mit einer Seite von Null Länge erkennen).

Wenn Ihre Polygone (möglicherweise) konkav sind, müssen Sie einige Trapezoide basierend auf der im Text erwähnten Fahrtrichtung Y (n) -Y (n + 1) verwerfen.

Jetzt haben Sie die Aufzählungspunkte in einem Polygon auf die Aufzählung von Punkten in einer Reihe von Trapezoiden reduziert. Das sollte nicht zu schwer sein, insbesondere wenn die Trapezoide gut ausgerichtet sind und zwei Linien parallel zur X-Achse "eingefangen" werden. Es ist wahrscheinlich am einfachsten zu tun , dass in einem Raster - Scan , so dass Sie nur den Start X und Ende X jede Rasterzeile berechnen haben.

Ihre Datenstruktur sieht möglicherweise aus wie eine Liste von Polygonen, ein Index, der angibt, in welchem ​​Polygon Sie sich befinden, welche x- und y-Koordinaten Sie haben und der Endindex der Rasterzeile, in der Sie sich befinden.

Ich gehe davon aus, dass es Ihnen nichts ausmacht, in welcher Reihenfolge Sie aufzählen!

Weitere Komplexität entsteht, wenn Ihre "Polygone" disjunkte Formen enthalten (dh tatsächlich mehr als ein Polygon oder polygonale "Löcher" enthalten könnten.

Die Komplexität des Erhaltens der Trapezoide ist ziemlich gering, aber das Iterieren über eine große Anzahl von Punkten kann ziemlich langsam sein. Ich habe keine Ahnung, wofür Sie dies tun, aber wie Stephane Hockenhull über ein herkömmliches Gewicht hinausführt, um es einfacher zu machen, ist es, eine Vergröberungsnäherung zu verwenden.

Das würde bedeuten, tatsächlich in Schritten von (sagen wir) 5 zu scannen und (wenn Ihr Algorithmus verständlich ist) den Mittelpunkt einer 5 * 5-Zelle als irgendwie repräsentativ zu behandeln.

Ich hoffe, Sie haben nicht nach einer einfachen Antwort gesucht? Ich würde gerne einen Code dafür sehen!