点多边形算法有时会给出错误的结果 [英] Point in Polygon algorithm giving wrong results sometimes

问题描述

我在StackOverflow上看到了我在PHP代码中实现的多边形中的点"光线跟踪算法.在大多数情况下，它运行良好，但是在某些复杂的情况下，如果具有复杂的多边形和恶性点，它会失败，并指出该点不在多边形中.

I saw on StackOverflow a "point in polygon" raytracing algorithm that I implemented in my PHP Code. Most of the time, it works well, but in some complicated cases, with complex polygons and vicious points, it fails and it says that point in not in polygon when it is.

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

For example:
You will find here my Polygon and Point classes: pointInPolygon method is in Polygon class. At the end of the file, there are two points that are supposed to lie inside the given polygon (True on Google Earth). The second one works well, but the first one is buggy :( .

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

推荐答案

去过那里:-)我还通过了stackoverflows PiP建议，包括您的参考资料和

Have been there :-) I also travelled trough stackoverflows PiP-suggestions, including your reference and this thread. Unfortunelaty none of the suggestions (at least those I tried) were flawless and sufficient for a real life scenario : like users plotting complex polygon on a google map in freehand, "vicious" right vs left issues, negative numbers and so on.

即使多边形包含数十万个点(例如县境，自然公园等)，PiP算法也必须在所有情况下都有效-不管多边形有多疯狂".

The PiP-algorithm must work in all cases, even if the polygon consists of hundred thousands of points (like a county-border, nature park and so on) - no matter how "crazy" the polygon is.

因此，我最终根据天文学应用程序的某些来源建立了一个新的算法:

So I ended up building a new algoritm, based on some source from an 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 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算法"不同，到目前为止，还没有任何抱怨.在此处(国家真菌学数据库，为丹麦人感到遗憾)中查看.您可以绘制多边形或选择公社"(县)-最终将具有数千个点的多边形与成千上万条记录进行比较.

It is now more than a year since i switched to the above algorithm on several sites. Unlike the "SO-algorithms" there has not been any complains so far. See it in action here (national mycological database, sorry for the danish). You can plot a polygon, or select a "kommune" (a county) - ultimately compare a polygon with thousands of points to thousands of records).

更新 请注意，此算法的目标是非常精确的地理数据/lat，lngs(小数点第n个)，因此将在多边形中"视为内部多边形-而不是在多边形边界上的 . 1,1被认为在外面，因为它在边界上. 1.0000000001,1.01不是.

Update Note, this algorithm is targeting geodata / lat,lngs which can be very precise (n'th decimal), therefore considering "in polygon" as inside polygon - not on border of polygon. 1,1 is considered outside, since it is on the border. 1.0000000001,1.01 is not.

这篇关于点多边形算法有时会给出错误的结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！