3

順序付けられたポイントのセットと、それらのポイントの近くにある順序付けられたlat、lonポイントで構成されるパス（緯度/経度座標）が与えられた場合、理想的にはアルゴリズムの複雑さ（n * log）を使用して、ポイントをパスに関連付けます。 （n））またはそれ以上ですが、それは現実的ではないかもしれません。

次の図は、私の質問をよりよく示しています。青い線は提供された順序付けられたパスであり、赤い点は青い線と同じ順序です。緑のパスは私の望ましい結果であり、赤い点と青い線を新しい順序付けられたパスにマージします。

質問を説明する図

青いパスから赤いポイントまでの距離にしきい値を設定する必要があります。赤いポイントが青いパスから最大50メートル離れていると仮定します。

だから、これは間違いなく私がStackOverflowで尋ねた中で最も数学的で珍しい質問です。どんなアイデアもこれを解決するのに素晴らしいでしょう。これを使用して、GTFS形状データを停止時間を説明するトリップデータとマージし、オープンソースプロジェクトであるDepartAppに組み込むことを計画しています。

ご協力いただきありがとうございます！

4

4 に答える 4

2

私には、緯度/経度のポイントと赤のポイントの2つのポイントがあります。緯度/経度のポイントの1つが出発点です。ここで、他のすべてのポイントをセットとして考慮し、（近似？）最近傍アルゴリズムを使用して次のポイントを見つけます。ここで繰り返します。唯一の問題は、最近傍アルゴリズムがO（n）になる傾向があることです。これにより、実行したいことがO（n ^ 2）になります。

于 2011-07-07T04:47:08.017 に答える
2

ここで提供されている他の提案に基づいて、効果的に機能するO（n）アルゴリズムを見つけたと思います。

アイデアは、最初に最初の赤い点を開始点として選択することです（または最初の青い点を選択することもできます）。次に、このポイントから次の赤いポイントおよび次の青いポイントまでの距離を比較し、近い方を選択します。両方のリストが使い果たされるまで繰り返します。これは、Translinkデータセットで非常に効果的であるようです。このアイデアを微調整したら、最新情報をお知らせします。

于 2011-07-08T03:15:51.123 に答える
1

赤い点ごとに青いセグメントを繰り返し、それに最適なセグメントを見つけます。正確に「最良」とはタスクによって異なりますが、「パスがどれだけ長くなるか」が適切な尺度になるように見えます。Aが赤い点で、BCがセグメントの場合、最良のセグメントはこれを最小化します：f（A、BC）=（| BA | + | AC |-| BC |）。

最適なセグメントが見つかったら、BAとACに置き換える必要があります。同様に、他のポイントも処理する必要があります。

最適化を行わないと、O（N ^ 2）が得られます。

ポイントがほぼ均一に分散され、セグメントの長さが図全体のサイズよりも大幅に短い場合は、スペースの分割が役立つ場合があります。

于 2011-07-07T05:19:52.673 に答える
1

おそらく、カスタムスイープラインアルゴリズムを使用できます。これにより、最も近いラインセグメントを見つける複雑さが軽減されます。

于 2011-07-07T15:17:29.680 に答える