指向Polygon算法有时会产生错误的结果

Question

我在StackOverflow上看到了我在PHP代码中实现的"多边形点"光线跟踪算法.大多数情况下,它运作良好,但在一些复杂的情况下,复杂的多边形和恶性点,它会失败,并且它表示不是多边形时的点.

例如:
您将在此处找到我的Polygon和Point类:pointInPolygon方法位于Polygon类中.在文件的末尾,有两个点应该位于给定的多边形内(Google地球上为True).第二个很好,但第一个是马车:(.

您可以使用此KML文件轻松检查Google地球上的多边形.

Answer 1

一直在那里:-)我也通过stackoverflows PiP建议,包括你的参考和这个线程.不幸的是,没有任何建议(至少是我尝试过的那些)对于现实生活场景来说是完美无缺的:就像用户在写意图中在谷歌地图上绘制复杂多边形,"恶意"右对左边问题,负数等等.

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"(县) - 最终将具有数千个点的多边形与数千个记录进行比较).

更新 注意,此算法的目标是geodata/lat,lngs可以非常精确(十进制小数),因此将"in polygon"视为内部多边形 - 而不是多边形的边界.1,1被认为是在外面,因为它在边界上.1.0000000001,1.01不是.