Punkt w algorytmie Wielokąta dając złe wyniki czasami

Question

Widziałem na StackOverflow "punkt w wielokącie" algorytmu raytracing, który zaimplementowałem w moim Kodzie PHP. W większości przypadków działa dobrze, ale w niektórych skomplikowanych przypadkach, ze złożonymi wielokątami i błędnymi punktami, kończy się niepowodzeniem i mówi, że punkt nie jest w wielokącie, kiedy jest.

Na przykład:
Znajdziesz here moje klasy Polygon i punkty: metoda pointInPolygon jest w klasie Polygon. Na końcu pliku znajdują się dwa punkty, które powinny leżeć wewnątrz danego wielokąta (True na Google Earth). Drugi działa dobrze, ale pierwszy jest buggy :(.

Można łatwo sprawdzić wielokąt na Google Earth za pomocą this KML file.

Answer 1

Zostały tam :-) Ja też podróżował koryta stackoverflows PIP-sugestii, w tym Twój numer referencyjny i this thread. Niefortunnie żadna z sugestii (przynajmniej tych, które próbowałem) była bezbłędna i wystarczająca dla scenariusza z prawdziwego życia: jak użytkownicy układający skomplikowany wielokąt na mapie google w trybie "od ręki", "błędne" w prawo w lewo, w negatywie i tak dalej.

Algorytm PiP musi działać we wszystkich przypadkach, nawet jeśli wielokąt składa się z setek tysięcy punktów (jak granica powiatu, park przyrody itp.) - bez względu na to, jak "szalony" jest wielokąt.

Więc skończyło się na budowę nowego algorytm, na podstawie jakiegoś źródła z astronomii-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; 
} 

Przykładem testu:

$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); 

Wyjścia:

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 

Minął ponad rok, odkąd przełączyłem się na powyższy algor ithm na kilku stronach. W przeciwieństwie do "SO-algorytmów" do tej pory nie było żadnych skarg. Zobacz go w akcji here (krajowa baza mikologiczna, przepraszam za duński). Możesz narysować wielokąt lub wybrać "kommune" (region) - ostatecznie porównaj wielokąt z tysiącami punktów do tysięcy rekordów).

Aktualizacja Uwaga, ten algorytm jest kierowana Geodata/szer LNGS które mogą być bardzo precyzyjna (n'th po przecinku), więc biorąc pod uwagę „w wieloboku” jako wewnątrz wielokąta - nie na granicy wielokąta . 1,1 jest uważany na zewnątrz, ponieważ jest na granicy. 1.0000000001,1.01 nie jest.