Ich habe in StackOverflow einen "Point in Polygon" Raytracing Algorithmus gesehen, den ich in meinem PHP Code implementiert habe. Die meiste Zeit funktioniert es gut, aber in einigen komplizierten Fällen, mit komplexen Polygonen und bösartigen Punkten, versagt es und es sagt, dass Punkt nicht im Polygon ist, wenn es ist.
Zum Beispiel:
Sie finden hier meine Polygon- und Point-Klassen: Die pointInPolygon-Methode befindet sich in der Polygon-Klasse. Am Ende der Datei befinden sich zwei Punkte, die innerhalb des angegebenen Polygons liegen sollen (True auf Google Earth). Die zweite funktioniert gut, aber die erste ist fehlerhaft :(.
Sie können das Polygon in Google Earth einfach mit dieser KML-Datei überprüfen.
War da :-) Ich bin auch durch Stapel-PiP-Vorschläge gereist, einschließlich Ihrer Referenz und Dieser Thread . Leider war keiner der Vorschläge (zumindest die, die ich ausprobiert hatte) makellos und ausreichend für ein reales Lebensszenario: wie Benutzer komplexe Polygone auf einer Google Map in Freihand, "bösartige" rechte vs linke Ausgaben, negative Zahlen und so weiter.
Der PiP-Algorithmus muss in allen Fällen funktionieren, auch wenn das Polygon aus Hunderttausenden von Punkten besteht (wie ein County-Grenze, Naturpark usw.) - egal wie "verrückt" das Polygon ist.
>Also habe ich am Ende einen neuen Algorithmus erstellt, basierend auf einer Quelle aus einer Astronomie-App:
%Vor%Illustrativer Test :
%Vor%Ausgaben:
%Vor%Es ist nun mehr als ein Jahr her, dass ich an mehreren Stellen zum obigen Algorithmus wechselte. Im Gegensatz zu den "SO-Algorithmen" gab es bisher keine Beschwerden. Sehen Sie es in Aktion hier (nationale mykologische Datenbank, Entschuldigung für das dänische). Sie können ein Polygon zeichnen oder eine "Kommune" (eine Grafschaft) auswählen - schließlich ein Polygon mit Tausenden von Punkten mit Tausenden von Datensätzen vergleichen.
Aktualisieren Beachten Sie, dass dieser Algorithmus auf Geodaten / Breitengrade abzielt, die sehr genau sein können (n-te Dezimalzahl) und daher "im Polygon" als innerhalb des Polygons - nicht am Rand des Polygons . 1,1 wird außerhalb betrachtet, da es an der Grenze ist. 1.0000000001,1.01 ist nicht.