Punto nell'algoritmo Poligono che fornisce risultati errati a volte

Question

Ho visto su StackOverflow un algoritmo di raytracing "punto in poligono" che ho implementato nel mio codice PHP. La maggior parte delle volte funziona bene, ma in alcuni casi complicati, con poligoni complessi e punti feroci, fallisce e dice che non è in poligono quando lo è.

Ad esempio:
Troverete here le mie classi Poligono e Punto: il metodo pointInPolygon è in classe Poligono. Alla fine del file, ci sono due punti che dovrebbero trovarsi all'interno del poligono dato (Vero su Google Earth). Il secondo funziona bene, ma il primo è buggy :(.

È possibile controllare facilmente il poligono su Google Earth utilizzando this KML file.

Answer 1

Ci sono stata :-) Ho anche viaggiato trogolo stackoverflows PIP-suggerimenti, incluso il tuo riferimento e this thread. Purtroppo nessuno dei suggerimenti (almeno quelli che ho provato) erano impeccabili e sufficienti per uno scenario di vita reale: come gli utenti che complottavano il complesso poligono su una mappa di google a mano libera, "vizioso" tra destra e sinistra, numeri negativi e così via.

L'algoritmo PiP deve funzionare in tutti i casi, anche se il poligono è composto da centinaia di migliaia di punti (come un confine della contea, un parco naturale e così via) - non importa quanto sia "pazzo" il poligono.

così ho finito per la costruzione di un nuovo algoritmo, sulla base di qualche fonte da un astronomia-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; 
} 

prova illustrativa:

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

Uscite:

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 

È passato più di un anno da quando sono passato al suddetto algoritmo ithm su diversi siti. A differenza degli "algoritmi SO" non ci sono state lamentele fino ad ora. Guardalo in azione here (database micologico nazionale, scusa per il danese). Puoi tracciare un poligono o selezionare un "kommune" (una contea), in ultima analisi, confrontare un poligono con migliaia di punti e migliaia di record. Aggiornamento

Nota, questo algoritmo si rivolge geodati/lat, LNGS che possono essere molto precisi (decimale n'th), quindi considerare "in poligono", come all'interno del poligono - non sul confine del poligono . 1,1 è considerato esterno, dal momento che è su il confine. 1.0000000001,1.01 non lo è.