Я видел в StackOverflow алгоритм ratracing, «точка в полигоне», который я реализовал в своем PHP-коде. В большинстве случаев это работает хорошо, но в некоторых сложных случаях с сложными полигонами и порочными точками он терпит неудачу и говорит, что точка не в полигоне, когда она есть.
Например:
Здесь вы найдете мои классы Polygon и Point: метод pointInPolygon находится в классе Polygon. В конце файла есть две точки, которые должны находиться внутри заданного многоугольника (True на Google Earth). Второй работает хорошо, но первый из них глючит :(.
Вы можете легко проверить многоугольник на Google Earth с помощью этого KML-файла .
Были там 🙂 Я также путешествовал по stackoverflows PiP-предложениям, включая вашу ссылку и эту тему . К сожалению, ни одно из предложений (по крайней мере, те, что я пробовал) было безупречным и достаточным для сценария реальной жизни: например, пользователи, планирующие сложный многоугольник на карте google в свободном доступе, «злобные» права против левых проблем, отрицательные числа и т. Д.
PiP-алгоритм должен работать во всех случаях, даже если многоугольник состоит из сотен тысяч точек (например, уездной границы, природного парка и т. Д.) – независимо от того, насколько «сумасшедшим» является многоугольник.
Поэтому я закончил создание нового алгоритма, основанного на каком-то источнике астрономии-приложения:
//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; } Иллюстративный тест :
$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);
Выходы:
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
Прошло уже больше года с тех пор, как я переключился на вышеупомянутый алгоритм на нескольких сайтах. В отличие от «SO-алгоритмов» до сих пор не было никаких жалоб. См. Здесь в действии (национальная микологическая база данных, извините за датскую). Вы можете построить многоугольник или выбрать «kommune» (графство) – в конечном счете сравнить многоугольник с тысячами точек до тысяч записей).
Update Note, этот алгоритм нацелен на геоданные / lat, lngs, которые могут быть очень точными (n-ый десятичный), поэтому рассматривая «в полигоне» как внутри многоугольника – не на границе полигона . 1,1 считается вне, так как он находится на границе. 1.0000000001,1.01 нет.