php - Point in Polygon algorithm giving wrong results sometimes -

php - Point in Polygon algorithm giving wrong results sometimes -

i saw on stackoverflow "point in polygon" raytracing algorithm implemented in php code. of time, works well, in complicated cases, complex polygons , vicious points, fails , says point in not in polygon when is.

for example: find here polygon , point classes: pointinpolygon method in polygon class. @ end of file, there 2 points supposed lie within given polygon (true on google earth). sec 1 works well, first 1 buggy :( .

you can check polygon on google earth using this kml file.

have been there :-) travelled trough stackoverflows pip-suggestions, including reference , this thread. unfortunelaty none of suggestions (at to the lowest degree tried) flawless , sufficient real life scenario : users plotting complex polygon on google map in freehand, "vicious" right vs left issues, negative numbers , on.

the pip-algorithm must work in cases, if polygon consists of hundred thousands of points (like county-border, nature park , on) - no matter how "crazy" polygon is.

so ended building new algoritm, based on source astronomy-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 operates (hundred)thousands of points set_time_limit(60); $c = 0; $p1 = $polygon[0]; $n = count($polygon); ($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 number of edges passed through even, it's not in poly. homecoming $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 .' within polygon<br>' : $ll.' outside<br>'; } test(2, 2); test(1, 1); test(1.5333, 2.3434); test(400, -100); test(1.01, 1.01);

outputs :

2,2 within polygon 1,1 outside 1.5333,2.3434 within polygon 400,-100 outside 1.01,1.01 within polygon

it more year since switched above algorithm on several sites. unlike "so-algorithms" there has not been complains far. see in action here (national mycological database, sorry danish). can plot polygon, or select "kommune" (a county) - compare polygon thousands of points thousands of records).

update note, algorithm targeting geodata / lat,lngs can precise (n'th decimal), hence considering "in polygon" inside polygon - not on border of polygon. 1,1 considered outside, since on border. 1.0000000001,1.01 not.

php polygon pip precision point