去过那里 :-) 我还浏览了 Stackoverflow 的画中画建议,包括您的参考和这个线程 https://stackoverflow.com/questions/5065039/find-point-in-polygon-php。不幸的是,没有一个建议(至少是我尝试过的)对于现实生活场景来说是完美的和足够的:比如用户在谷歌地图上徒手绘制复杂的多边形,“恶性”的左右问题,负数等等。
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 算法”不同,到目前为止还没有任何投诉。查看实际效果here http://svampe.dk/soeg/(国家真菌学数据库,对不起丹麦人)。您可以绘制一个多边形,或选择一个“kommune”(一个县) - 最终将具有数千个点的多边形与数千条记录进行比较)。
Update请注意,该算法的目标是地理数据/纬度,经度,它可以非常精确(第n位小数),因此将“在多边形中”视为内多边形 - not 在多边形的边界上。 1,1 被视为外部,因为它是on边界。 1.0000000001,1.01 不是。