点在多边形算法有时给出错误结果

Question

点在多边形算法有时给出错误结果

phppolygonprecision

16

我在StackOverflow上看到了一个“点在多边形内”的光线追踪算法，我将它实现在了我的PHP代码中。大部分时间它都能正常工作，但是在一些复杂的情况下，例如复杂的多边形和奇特的点时，它会失败并说这个点不在多边形内。

例如：
你可以在这里找到我的多边形和点类：pointInPolygon方法在Polygon类中。文件末尾有两个点，它们应该位于给定的多边形内部（在Google Earth上验证正确）。第二个点能够正常工作，但第一个点存在漏洞:(。

你可以使用这个KML文件轻松检查多边形在Google Earth上的位置。

- user1527491

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- davidkonrad · Accepted Answer

我也去过那里 :-) 我还通过Stackoverflow的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”（县）-最终将一个由数千个点组成的多边形与数千条记录进行比较）。

更新请注意，此算法针对可以非常精确（第n位小数）的地理数据/纬度、经度，因此将“in polygon”视为多边形内部，而不是多边形边界上。1,1 被认为是外部，因为它在边界上。1.0000000001,1.01 不是。