0

英国の各道路のすべてのウェイポイントを含むデータベースがあります。

ユーザーの緯度と経度を指定して、データベースから最も近い道路を計算し、名前を表示するナビゲーションアプリを構築しようとしています

データベースの JSON 表現のスニペット

[
{
    "NAME": "Trinity Road",
    "coordinates": [
        [
            1.7595267,
            52.4778475
        ],
        [
            1.7587864,
            52.4774
        ]
    ]
},
{
    "NAME": "Wilde Street",
    "coordinates": [
        [
            1.7593497,
            52.4795499
        ],
        [
            1.7594677,
            52.4795041
        ],
        [
            1.7598164,
            52.4793277
        ]
    ]
}
]

私が直面した問題は、最寄りの道路を正しく見つけることです。与えられたポイントが最も近いパス/ラインを見つける適切なアルゴリズムが見つかりません

最も近い道路が 2 つのウェイポイントの間にある可能性があるため、座標を単純に比較することはできません (「最も近いポイントのペアの問題」を除外します)。

誰かが適切なアルゴリズムを提案できますか?

私が考えることができる最善の解決策は、ユーザーへの近さに応じて道路に重みがあり、ユーザーをすぐに囲む最も価値の高い道路を選択する加重グリッド/マトリックスです (ただし、これは高価になる可能性があります)。

GoogleマップなどのWeb APIやPostGISを使用せずにこれを解決したいと思います(sqlite-モバイルアプリを使用する必要があります)

4

2 に答える 2

0

四分木を使用することは、検索スペースを制限するための正しいアプローチです。クワッド ノードごとに 100 を超えるラインがないように、クワッド ツリーをパラメーター化します。

(複雑な) ボロノイ図は必要ありません。

クワッド ツリーでの検索後、結果はクワッド ノードに重なる行のリストになります。

distanceToLineSegment(Point, point0, point1); を使用します。（その名前でインターネットを検索してください）

最短距離を取る。

distanceToLineSegment を呼び出す前に、ポイントがデカルト空間にあるように、その場でポイントを変換する必要があります。クワッド ノードの中心を変換中心として使用します。

于 2014-07-25T08:31:17.003 に答える