2 つの多角形間の最短のデカルト距離を見つける最も簡単な方法は何ですか?
https://stackoverflow.com/questions/84034
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は持っている 赤いポリゴン 1 個 言って、 ランダムに配置された 50 個の青いポリゴン - 地理的に位置する 2D空間. 。赤い多角形とそれに最も近い青い多角形の間の最短距離を見つけるための最も迅速なアルゴリズムは何ですか?
多角形の頂点を構成する点が必ずしも最も近い点であるとは限らないため、それらの点を距離をテストするための値として取得するのは単純なケースではないことに留意してください。
したがって、最終的に、答えは、単一の赤い多角形に最も近い青い多角形を返す必要があります。
これは思っているより難しいです！
解決
赤いものとすべての青いものの間の距離を計算し、それらを長さによって分類するよりも良い解決策があるとは思えません。
並べ替えに関しては、通常、QuickSort はパフォーマンスで勝るのは困難です (サイズが 7 項目を下回ると再帰を遮断し、InsertionSort (おそらく ShellSort など) に切り替わる最適化されたもの)。
したがって、問題は 2 つのポリゴン間の距離をどのように迅速に計算するかということだと思います。結局のところ、この計算を 50 回行う必要があるのです。
次のアプローチは 3D にも同様に機能しますが、おそらく最速のアプローチではありません。
問題は、スピードを犠牲にして精度を犠牲にしてもよいかということです。例えば。すべてのポリゴンを境界ボックスに詰めることができます。この場合、ボックスの辺は座標系の軸と平行になります。3D ゲームではこのアプローチが頻繁に使用されます。したがって、仮想境界ボックスを構築するには、すべての座標 (x、y、z) の最大値と最小値を見つける必要があります。これらの境界ボックスの距離を計算することは、非常に簡単な作業になります。
以下は、座標系の軸に平行ではない、より高度な境界ボックスの画像例です。
ただし、これにより距離の計算が簡単ではなくなります。これは、距離を知る必要がなく、ある境界ボックスの 1 つのエッジが別の境界ボックス内にあるかどうかだけを知る必要があるため、衝突検出に使用されます。
次の図は、軸が整列された境界ボックスを示しています。
OOB はより正確で、AABB はより高速です。もしかしたら、この記事を読んでみたいかもしれません:
これは常に、速度のために精度を犠牲にする意思があることを前提としています。速度よりも精度が重要な場合は、より高度なテクニックが必要になる場合があります。
他のヒント
問題を軽減してから、小規模なセットに対して集中的な検索を実行できる場合があります。
まず次のことを見つけて各ポリゴンを処理します。
- 多角形の中心
- ポリゴンの最大半径 (つまり、定義された中心から最も遠いポリゴンのエッジ/サーフェス/頂点上の点)
これで、たとえば、赤いポリゴンに最も近い 5 ～ 10 個のポリゴンを収集し (中心間の距離を求め、半径を減算し、リストを並べ替えて上位 5 つを取得します)、さらに徹底的なルーチンを実行できます。
GIS やゲーム アプリケーションなど、適度な数の境界点を持つポリゴン シェイプの場合は、一連のテストを実行するほうが簡単な場合があります。
赤いポリゴンの各頂点について、青いポリゴンの各頂点までの距離を計算して、最も近いものを見つけます（ヒント、距離を比較^2でsqrt（）が必要ないように）最も近いものを見つけてから、両側の頂点を確認します発見された赤と青の頂点のうち、どの線セグメントが最も近いかを決定し、2つのラインセグメント間で最も近いアプローチを見つけます。
見る http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ (2Dの場合は簡単です)
このスクリーニング手法は、結果の精度を損なうことなく、平均的なケースで実行する必要がある距離計算の数を減らすことを目的としています。凸面ポリゴンと凹面ポリゴンで動作します。
1 つが赤色の頂点、もう 1 つが青色の頂点となる、頂点の各ペア間の最小距離を見つけます。あれを呼べ r. 。ポリゴン間の距離は最大で r. 。赤いポリゴンから各線分を外側に移動した新しい領域を構築します。 r 半径の円弧によって隣接するものと結合されています r 頂点を中心にしています。この領域内の各頂点から、この領域と交差する反対色のすべての線分までの距離を求めます。
もちろん、境界ボックスなどの近似方法を追加して、どの青いポリゴンが赤い領域と交差する可能性がないのかをすばやく判断することもできます。
おそらく Frechet Distance があなたが探しているものでしょうか?
「最短距離」と言ったのはわかりますが、本当に問題に対して最適な解決策、または「良い/非常に良い」解決策が適切であるという意味でしょうか?
最適なソリューションを見つける必要がある場合は、すべてのソース ポリゴン境界と宛先ポリゴン境界 (頂点だけでなく) の間の距離を計算する必要があるためです。3D 空間にいる場合、各境界は平面になります。頂点の数によっては、これは大きな問題 (O(n^2)) になる可能性があります。
したがって、頂点数が恐ろしい数に達し、かつ「良好/非常に良好」な解決策で問題ない場合は、ヒューリスティックな解決策または近似を使用してください。
ボロノイ カリングを見てみるのもいいかもしれません。論文とビデオはこちらから:
まず、すべてのポリゴンを境界円で囲み、次に最小距離の上限を見つけます。次に、距離の下限が最小距離の上限よりも小さいすべての青いポリゴンのエッジを、赤いポリゴンのすべてのエッジに対してチェックするだけです。
upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}
for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
check distance of edges and vertices
しかし、それはすべてデータに依存します。青いポリゴンが赤いポリゴンとの間の距離に比べて比較的小さい場合、このアプローチは適切に機能しますが、それらが非常に近い場合は何も保存されません (それらの多くは十分に近いでしょう)。そしてもう 1 つ -- これらのポリゴンに多くの頂点がない場合 (ポリゴンのほとんどが三角形である場合など)、各赤いエッジを各青いエッジと比較するだけでほぼ同じ速度になる可能性があります。
それが役に立てば幸い
他の人が述べたように、境界領域（ボックス、円）を使用すると、一部のポリゴン間の相互作用を破棄できる可能性があります。これにはいくつかの戦略があります。
- 任意の青いポリゴンを選択し、赤いポリゴンからの距離を見つけます。次に、他のポリゴンを選択します。境界領域間の最小距離がすでに見つかった距離より大きい場合は、この多角形を無視できます。すべてのポリゴンに対して続行します。
- 赤いポリゴンとすべての青いポリゴンの間の最小距離/重心距離を見つけます。距離を並べ替えて、最初に最小距離を検討します。実際の最小距離を計算し、ポリゴン間の最大距離がこれまでに見つかった最小距離より大きくなるまで、並べ替えられたリストを処理し続けます。
円/軸方向に整列したボックス、または方向付けされたボックスの選択は、入力ポリゴンの実際のレイアウトに応じて、アルゴリズムのパフォーマンスに大きな影響を与える可能性があります。
実際の最小距離の計算には、Yang らの 'ボロノイ図に基づいて 2 つの互いに素な凸多角形間の距離を計算する新しい高速アルゴリズム' これは O(log n + log m) です。
すぐにお葬式に逃げなければなりませんが、ポリゴンを凸サブポリゴンに分割すると、実行できる最適化がいくつかあります。各ポリゴンに対してバイナリ検索を実行して、最も近い頂点を見つけることができます。 信じる 最も近い点は、その頂点または隣接するエッジのいずれかである必要があります。これは、次の条件で実行できるはずであることを意味します log(log m * n) ここで、m はポリゴン上の平均頂点数、n はポリゴンの数です。急ぎ足なので間違っているかもしれません。ご希望に応じて、後ほど詳細をお知らせします。
まず、境界ボックス間の距離を比較することから始めることができます。四角形間の距離をテストすることは、多角形間の距離をテストするよりも簡単で、nearest_rect + its_diagonal よりも離れている多角形をすぐに削除できます (さらに調整できる可能性があります)。次に、残りのポリゴンをテストして、最も近いポリゴンを見つけます。
ポリゴンの近接性を見つけるためのアルゴリズムがあります。Wikipedia にそれらについての良いレビューがあると思います。私の記憶が正しければ、凸多角形のみを許可するものの方が大幅に高速です。
あなたが探しているのは、経路探索に使用される A* アルゴリズムだと思います。
素朴なアプローチは、赤のオブジェクトと 50 個の青のオブジェクトの間の距離を見つけることです。つまり、答えを見つけるために 50 個の 3D ピタゴラス計算と並べ替えを確認することになります。ただし、これは中心点間の距離を見つける場合にのみ機能します。
任意のポリゴンが必要な場合、おそらく最善の方法は、法線を基準にして赤いポリゴンの表面から光線を放射し、別のポリゴンがヒットしたときにレポートするレイトレーシング ソリューションです。
ハイブリッドが機能する可能性があります。青いポリゴンの相対的なサイズについてある程度の概念があると仮定して、中心点からの距離を見つけることができ、それらの中で最も近い結果セットを選択し、レイトレーシングを使用して真のポリゴンを絞り込むことができます。最も近いポリゴン。
