16

StackOverflowで、PHPコードに実装した「ポリゴンの点」レイトレーシングアルゴリズムを見ました。ほとんどの場合、それはうまく機能しますが、複雑なポリゴンと悪意のあるポイントがある複雑なケースでは、失敗し、そのポイントがポリゴン内にない場合にそのポイントを表示します。

例：ここ
に私のPolygonクラスとPointクラスがあり ます。pointInPolygonメソッドはPolygonクラスにあります。ファイルの最後に、指定されたポリゴンの内側にあると想定される2つのポイントがあります（Google EarthではTrue）。2つ目はうまく機能しますが、1つ目はバグがあります:(。

このKMLファイルを使用して、GoogleEarthでポリゴンを簡単に確認できます。

4

1 に答える 1

54

そこに行ったことがある:-)私は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

いくつかのサイトで上記のアルゴリズムに切り替えてから1年以上になります。「SOアルゴリズム」とは異なり、これまでのところ苦情は​​ありません。ここで実際の動作を確認してください（国立真菌データベース、デンマーク語で申し訳ありません）。ポリゴンをプロットするか、「kommune」（郡）を選択できます。最終的には、数千のポイントを持つポリゴンを数千のレコードと比較します。

更新 注：このアルゴリズムは、非常に正確（小数点以下第2位）のgeodata / lat、lngsを対象としているため、「ポリゴン内」をポリゴンの境界ではなくポリゴンの内側と見なします。1,1は境界上にあるため、外側と見なされます。1.0000000001,1.01はそうではありません。

于 2013-08-12T15:00:15.283 に答える