多邊形算法中的點有時會給出錯誤的結果

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不是。