Algorithmus, um ein Polygon rekursiv in In/Out -Quadranten zu teilen: Wie heißt es und wo ist der Code?

Question

Ich habe viele Punkte (Hunderttausende) und möchte überprüfen, welche sich in einem Polygon befinden. Für ein relativ kleines Polygon (dh wahrscheinlich nur Zehn oder Hunderte von Punkten) kann ich einfach das Begrenzungskästchen des Polygons als Erstprüfung verwenden und dann eine regelmäßige Punkt-in-Poly-Prüfung für diese Punkte innerhalb des Feldes durchführen . Aber stellen Sie sich einen großen (dh wahrscheinlich Tausenden meiner Punkte) vor, unregelmäßig geformtes Polygon. Viele Punkte werden die Begrenzungskästchen überprüfen, und außerdem wird der Point-in-Poly-Scheck teurer sein, da das größere Polygon aus vielen weiteren Punkten besteht. Daher möchte ich in der Lage sein, die meisten Punkte ein- oder aus oder herauszufiltern, ohne die volle Point-in-poly-Überprüfung durchzuführen.

Ich habe also einen Plan, und hauptsächlich möchte ich wissen, ob das, was ich beschreibe, ein bekannter Algorithmus ist und wenn ja, wie es heißt und wo ich den vorhandenen Code dafür finde. Ich glaube nicht, dass das, was ich beschreibe, entweder ein Quad-Baum oder ein R-Tree ist, und ich weiß nicht, wie ich danach suchen soll. Ich nenne es unten einen "rechte Baum".

Die Idee ist, mit diesen größeren Polygonen umzugehen:

Führen Sie eine "rechte Baum" -Preprozess durch, wobei die Tiefe des rechte Baumes je nach Größe des Polygons variiert (dh eine mehr Tiefe für ein größeres Polygon). Der rechte Baum würde den Begrenzungsbox des Polygons in vier Viertel teilen. Es würde prüfen, ob sich jeder Viertelrektschaft vollständig innerhalb des Polygons befindet, vollständig außerhalb des Polygons oder beiden. Bei keiner würde es die Untereinstellungen rekursiv teilen und auf diese Weise fortgesetzt, bis alle Rektionen entweder innen oder außen waren oder die maximale Tiefe erreicht worden war. Die Idee ist also, dass (a) die Zeit vor dem Verarbeitung, diesen Baum herzustellen,, obwohl er selbst mehrere Punkt-in-Polygon-Überprüfungen durchführt, es wert ist, da diese Zeit durch die Anzahl der zu überprüfenden Punkte in den Schatten gestellt wird. und (b) die überwiegende Mehrheit der Punkte kann mit einfachen Begrenzungskästchen-Überprüfungen behandelt werden (im Allgemeinen einige solche Überprüfungen, wenn Sie den Baum absteigen), und dann müsste eine relativ kleine Zahl die volle Punkt-in-Polygon-Prüfung durchführen (achten Denn wenn Sie einen Blattknoten erreichen, der immer noch "weder" ist).

Wie heißt dieser Algorithmus? Und wo ist der Code? Es scheint tatsächlich nicht so schwer zu schreiben, aber ich dachte mir, ich würde fragen, bevor ich in die Codierung springe.

Answer 1

Ich habe tatsächlich einen verwandten, aber anderen Ansatz verwendet. Ich erkannte, dass diese Baumstruktur, die ich aufbaute, nicht mehr als das Polygon war, das bei einer geringen Auflösung gezogen wurde. Wenn mein Baum zum Beispiel in eine Tiefe von 8 ging, war das wirklich so, als würde man mein Polygon mit Auflösung 256x256 auf eine Bitmap zeichnen und dann Pixel -Treffer gegen dieses Polygon durchführend. Also habe ich diese Idee erweitert und eine schnelle Grafikbibliothek (die CIMG -Bibliothek) verwendet. Ich zeichne das Polygon auf eine schwarz-weiße Bitmap mit Größe 4000x4000. Dann überprüfe ich nur die Punkte als Pixel gegen diese Bitmap. Die Magie ist, dass das Zeichnen dieser riesigen Bitmap im Vergleich zu dem Zeitpunkt, an dem ich den Baum gebaut habe, sehr schnell ist. Ich bekomme also eine viel höhere Auflösung als ich jemals mit meinem Baum haben konnte.

Ein Problem ist es, Punkte in der Nähe des Randes des Polygons zu erkennen, die aufgrund von Rund-/Auflösungsproblemen auch bei 4000 x 4000er Größe falsch eingeschlossen oder ausgeschlossen werden können. Wenn Sie genau wissen müssen, ob diese Punkte ein- oder ausgerichtet sind, können Sie in einer anderen Farbe einen Schlag um das Polygon zeichnen, und wenn Ihr Pixel -Test diese Farbe erreicht hat, würden Sie den vollen Punkt in Poly -Check durchführen. Für meine Zwecke war die Auflösung von 4000 x 4000 gut genug (ich konnte für einige meiner Kantenpunkte die falsche Aufnahme/Ausschluss tolerieren).

Der grundlegende Trick dieser Lösung ist also die Idee, dass Polygon -Zeichnungsalgorithmen im Vergleich zu anderen Möglichkeiten, wie Sie Ihr Polygon "digitalisieren" könnten, nur sehr schnell sind.