19

ユーザーが地図上に複雑な多角形を描画できるようにしてから、特定の経度/緯度がその多角形内に存在するかどうかをアプリケーションに確認させる必要があります。

地球の曲率を補正しない単純な x/y デカルト座標系を使用しているアルゴリズムしか見つけることができませんでした。

ユーザーが PC でポリゴンを描画すると、ポイントが無線経由で組み込みデバイスに転送されます。デバイスは、指定されたポリゴンが現在の位置 (GPS から取得) 内にあるかどうかを確認する必要があります。

これは組み込みデバイス用であるため、巨大なライブラリを使用することはできません。むしろ、自分でチェックを実行するためのアルゴリズムまたは非常に小さなライブラリが必要です。しかし、そのようなアルゴリズムを見つけることができないようです。

4

2 に答える 2

17

これは、頂点のリストを含む Polygon クラス用に C# で作成した実装です。地球の曲率は考慮されていません。むしろ、これを実行する前に、ポリゴンを小さなセグメントに前処理します。

このアルゴリズムのパフォーマンスは非常に優れています。数千のエッジを持つポリゴンでも、デスクトップでは約 1 ～ 2 ミリ秒で完了します。

コードはかなり最適化されているため、疑似コードほど読みやすくはありません。

public bool Contains(GeoLocation location)
{
    if (!Bounds.Contains(location))
        return false;

    var lastPoint = _vertices[_vertices.Length - 1];
    var isInside = false;
    var x = location.Longitude;
    foreach (var point in _vertices)
    {
        var x1 = lastPoint.Longitude;
        var x2 = point.Longitude;
        var dx = x2 - x1;

        if (Math.Abs(dx) > 180.0)
        {
            // we have, most likely, just jumped the dateline (could do further validation to this effect if needed).  normalise the numbers.
            if (x > 0)
            {
                while (x1 < 0)
                    x1 += 360;
                while (x2 < 0)
                    x2 += 360;
            }
            else
            {
                while (x1 > 0)
                    x1 -= 360;
                while (x2 > 0)
                    x2 -= 360;
            }
            dx = x2 - x1;
        }

        if ((x1 <= x && x2 > x) || (x1 >= x && x2 < x))
        {
            var grad = (point.Latitude - lastPoint.Latitude) / dx;
            var intersectAtLat = lastPoint.Latitude + ((x - x1) * grad);

            if (intersectAtLat > location.Latitude)
                isInside = !isInside;
        }
        lastPoint = point;
    }

    return isInside;
}

基本的な考え方は、テスト対象のポイントの「x」位置にまたがる多角形のすべてのエッジを見つけることです。次に、ポイントの上に伸びる垂直線と交差する数を見つけます。偶数がポイントの上を横切る場合、ポリゴンの外側にいます。奇数が上を横切る場合は、内側です。

于 2012-12-19T11:13:30.823 に答える
7

必要に応じて変換できる適切な説明と簡単な C コード

http://alienryderflex.com/polygon/

ポリゴン チェックを RTree と組み合わせて、重複していないポリゴンが多数ある場合に検索ツリーをすばやくカリングします。

于 2014-07-21T15:27:23.103 に答える