4

私の質問は少し奇妙かもしれません。私はアルゴリズムを「開発」しましたが、同様のアルゴリズムがすでに存在するかどうかはわかりません。

状況：トラックポイント（2D）で定義されたトラックがあります。トラックポイントは、たとえばターンを表します。トラックポイントの間には直線しかありません。これで、この2D空間の一連の座標が与えられました。最初のトラックポイントから新しい座標までの距離と、最初の2つのトラックポイントの間隔の距離を計算します。測定された座標までの距離が最初のトラックポイントから2番目のトラックポイントまでの距離よりも短い場合、このポイントはこの間隔の間にあると想定します。次に、その上で線形補間を行います。大きい場合は、次の間隔で確認します。

つまり、基本的には間隔の距離を取り、そこにそれらを収めようとします。このトラックにほぼ沿って移動するオブジェクトを追跡しようとしています。

これは誰かに馴染みがあるように聞こえますか？誰かが同様の既存のアルゴリズムの提案を思い付くことができますか？

編集：これまでに述べたことから、位置がトラックポイントに多重に関連付けられていないことを明確にしたいと思います。ジョナサンが作成したすばらしいASCII描画について考えてみましょう。

X位置はセグメント1および2（S12）内にあることがわかります。次の位置はYです。これは、S12上にあるほど近くにあるとは見なされません。S23に移動し、S23が入っているかどうかを確認します。

入っている場合は、S12で他の値をチェックしません。これは、次のセグメントですでに1つ見つかっているためです。アルゴリズムは「振り返りません」。

しかし、それが最初のセグメントから遠く離れているが、それでも他のセグメントから遠く離れているために、そこから適切なセグメントが見つからない場合は、値をドロップして次の位置を探します再びS12に戻ります。

ループはまだ問題のままです。S23でYを取得し、2つまたは3つの位置をスキップすると（距離が遠すぎるため）、トラックを失う可能性があります。すでにS56にあるS34の1つの位置を特定できました。

たぶん、私はそれがどのセグメントであるべきかを判断するための平均速度を思い付くことができます。

セグメントが大きいほど、正しい決定を下す可能性が高くなるようです。

4

2 に答える 2

6

あなたが説明したアルゴリズムについて私が懸念しているのは、それが「貪欲」であり、「間違った」トラックセグメント（または、少なくとも、ポイントに最も近くないトラックセグメント）を選択できることです。

アスキーアートを限界まで押し上げる時が来ました。次のパス（番号はトラックポイントのリスト内のシーケンスを表します）と座標X（および後でY）を検討してください。

    1-------------2
                  |
                  |    Y
                X |
            5-----+-----6
            |     |
            |     |
            4-----3

私たちはあなたの説明をどのように解釈することになっていますか？

[C]最初のトラックポイントから新しい座標までの距離と、最初の2つのトラックポイントの間隔の距離を計算します。測定された座標までの距離が最初のトラックポイントから2番目のトラックポイントまでの距離よりも短い場合は、このポイントがこの間隔の間にあると想定します。[...] [i]大きい場合は、[...]次の間隔で確認してください。

私は最初の文が意味すると思います：

  • TP1（トラックポイント1）からTP2までの距離を計算します-それをD12と呼びます。
  • TP1からX（D1Xと呼びます）およびTP2からX（D2Xと呼びます）までの距離を計算します。

トリッキーな部分は、条件文の解釈です。

私の印象では、D1XまたはD2XのいずれかがD12より小さい場合、XはトラックセグメントTP1からTP2（セグメントS12と呼びます）上にある（または最も近い）と見なされます。

図のXの位置を見ると、D1XとD2Xの両方がD12よりも小さいことが適度に明らかです。したがって、アルゴリズムの解釈では、XはS12に関連付けられていると解釈されますが、Xは明らかにS23またはS56に近いです。 S12までです（ただし、それらは考慮されることなく破棄されます）。

私はあなたのアルゴリズムについて何か誤解しましたか？

少し考えてみてください。私があなたのアルゴリズムを意味すると解釈したのは、点XがTP1を中心とする半径D12の円、またはTP2を中心とする半径D12の円のいずれかにある場合、XをS12に関連付けるということです。ただし、ポイントYも考慮すると、使用することをお勧めするアルゴリズムは、それをS12にも関連付けます。

アルゴリズムが洗練されてMAX(D1Y, D2Y) < D12、となる場合、YはS12に関連しているとは見なされません。ただし、XはおそらくS23やS56ではなくS12に関連していると考えられています。

于 2009-08-23T11:35:02.510 に答える
1

このアルゴリズムの最初の部分は、離散化された空間を移動することを思い出させます。このような空間を表す例は、Z次の空間充填曲線です。私はこの手法を使用して、かつて取り組んだ適応メッシュ細分化コードのデータ構造である四分木を表現し、グリッドをトラバースして粒子間の距離を決定するために説明したものと非常によく似たアルゴリズムを使用しました。

類似性はすぐには明らかではないかもしれません。区間の位置のみを考慮しているため、このステップでは、区間上のすべてのポイントを同等として効果的に処理しています。これは、離散化されたポイントのみを持つスペースを選択するのと同じです。つまり、ポイントをグリッドに効果的に「スナップ」します。

于 2009-08-23T10:25:57.283 に答える