Punkt in Polygon-Algorithmus, der manchmal falsche Ergebnisse liefert

Question

Ich habe in StackOverflow einen "Punkt 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 here meine Polygon und Point-Klassen: pointInPolygon-Methode ist in 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 Buggy :(.

Sie leicht das Polygon auf Google Earth this KML file mit überprüfen können.

Answer 1

gab es :-) ich auch Trog stackoverflows BiB-Vorschläge gereist, einschließlich Ihrer Referenz und this 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 eine County-Grenze, Naturpark usw.) - egal wie "verrückt" das Polygon ist.

So landete ich ein neues algoritm Aufbau, basierend auf einer Quelle von einer Astronomie-App:

//Point class, storage of lat/long-pairs 
class Point { 
    public $lat; 
    public $long; 
    function Point($lat, $long) { 
     $this->lat = $lat; 
     $this->long = $long; 
    } 
} 

//the Point in Polygon function 
function pointInPolygon($p, $polygon) { 
    //if you operates with (hundred)thousands of points 
    set_time_limit(60); 
    $c = 0; 
    $p1 = $polygon[0]; 
    $n = count($polygon); 

    for ($i=1; $i<=$n; $i++) { 
     $p2 = $polygon[$i % $n]; 
     if ($p->long > min($p1->long, $p2->long) 
      && $p->long <= max($p1->long, $p2->long) 
      && $p->lat <= max($p1->lat, $p2->lat) 
      && $p1->long != $p2->long) { 
       $xinters = ($p->long - $p1->long) * ($p2->lat - $p1->lat)/($p2->long - $p1->long) + $p1->lat; 
       if ($p1->lat == $p2->lat || $p->lat <= $xinters) { 
        $c++; 
       } 
     } 
     $p1 = $p2; 
    } 
    // if the number of edges we passed through is even, then it's not in the poly. 
    return $c%2!=0; 
} 

Illustrative Test:

$polygon = array(
    new Point(1,1), 
    new Point(1,4), 
    new Point(4,4), 
    new Point(4,1) 
); 

function test($lat, $long) { 
    global $polygon; 
    $ll=$lat.','.$long; 
    echo (pointInPolygon(new Point($lat,$long), $polygon)) ? $ll .' is inside polygon<br>' : $ll.' is outside<br>'; 
} 

test(2, 2); 
test(1, 1); 
test(1.5333, 2.3434); 
test(400, -100); 
test(1.01, 1.01); 

Ausgänge:

2,2 is inside polygon 
1,1 is outside 
1.5333,2.3434 is inside polygon 
400,-100 is outside 
1.01,1.01 is inside polygon 

Es ist jetzt mehr als ein Jahr her, dass ich auf den obigen Algorithmus umgeschaltet habe ithm auf mehreren Seiten. Im Gegensatz zu den "SO-Algorithmen" gab es bisher keine Beschwerden. Sehen Sie es in Aktion here (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 Hinweis, dieser Algorithmus zielt Geodaten/lat, lngs, die sehr präzise (n-ten dezimal) sein kann, also "in Polygon" als innerhalb Polygon Berücksichtigung - nicht Rand des Polygons . 1,1 wird außerhalb betrachtet, da es auf der Grenze ist. 1.0000000001,1.01 ist nicht.