多边形算法中的点有时会给出错误的结果

Question

我在StackOverflow上看到了一个在我的PHP代码中实现的“点多边形”射线追踪算法。大多数情况下，它运行良好，但在一些复杂的情况下，具有复杂的多边形和恶性点时，它会失败，并且它在多边形中表示该点不在时。

例如：
我会发现here我的Polygon和Point类：pointInPolygon方法在Polygon类中。在文件末尾，有两点应该位于给定的多边形内（Google地球上为True）。第二个运作良好，但第一个是越野车:(。

可以使用this KML file很容易地检查在谷歌地球的多边形。

Answer 1

去过那里:-)我也走过低谷stackoverflows PIP-建议，包括你的参考和this thread。不幸的是，没有任何建议（至少我尝试过的）对于现实生活场景来说是完美无暇的：就像用户在徒手绘制谷歌地图上绘制复杂的多边形一样，“恶性”与左边的问题，负面的数字等等。

无论多边形多么“疯狂”，即使多边形由数十万个点组成（如县边界，自然公园等），PiP算法也必须适用于所有情况。

所以我最终建立一个新的algoritm的基础上，从天文应用中的一些来源：

//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 

现在已经超过一年了，因为我切换到上述算法ithm在几个网站上。与“SO算法”不同，到目前为止还没有任何抱怨。在行动here（国家真菌学数据库，对丹麦人抱歉）看到它。你可以绘制一个多边形，或选择一个“kommune”（一个县） - 最终比较一个多边形与数千个点到数千个记录）。在多边形的边界不-

更新 注意，该算法的目标是地理/ LAT，它可以非常精确（第n个十进制）LNGS，因此考虑到“多边形”作为内多边形 。 1,1被认为是外部的，因为它是上的的边界。 1.0000000001,1.01不是。