多边形算法中的点有时会给出错误的结果 [英] 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 地球上的多边形.

You can easily check the polygon on Google Earth using this KML file.

推荐答案

去过那里 :-) 我还浏览了 Stackoverflow 的 PiP-suggestions，包括您的参考和 这个线程.不幸的是，这些建议(至少我尝试过的建议)都没有完美且足以满足现实生活的场景:就像用户在谷歌地图上徒手绘制复杂的多边形一样，恶意"的右与左问题、负数等.

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

画中画算法必须适用于所有情况，即使多边形由数十万个点组成(如县边界、自然公园等)——无论其多么疯狂".多边形是.

The PiP-algorithm must work in all cases, even if the polygon consists of hundreds of 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 algorithm, 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 have not been any complaints 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屋！