algorithm - the - 2つのポリライン間の距離



performance computational-geometry (2)

分割統治:

  • 1組の折れ線とそれらの軸合わせ最小境界ボックス間の最小距離(AAMBB)を表すデータ構造を定義します。pair pair = (poly_a, poly_b, d_ab)

  • 距離d_abをキーとして使用して、 pairデータ構造用の空のキューを作成します。

  • 初期ポリラインを使用してpairデータ構造を作成し、それをキューにプッシュします。

  • これまでに見つかったポリライン間の最小距離( min_d )で変数を保持します。 無限大に設定してください。

  • 繰り返す:

    • 最小距離d_ab要素をキューからポップします。

    • d_abd_abより大きい場合は終了です。

    • ポリラインpoly_aまたはpoly_bいずれかに唯一のセグメントが含まれる場合:

      • その間の最小距離を見つけるために総当たりを使用し、それに応じてmin_dを更新します。
    • さもないと:

      • ポリラインpoly_apoly_b両方を半分に分割します。例えば、

        (1-7) --> { (1-4), (4-7) }

        (8-12) --> { (8-10), (10-12) }

      • 両方のセットのクロス積を作成し、4つの新しいpairデータ構造を作成してからキューQにプッシュします。

平均して、複雑さはO(N * log N)、最悪の場合はO(N 2)です。

更新 :Perlで実装されたalgorithm

2つのポリライン間の距離dを計算します。

明らかに私はすべての線分のペアの距離を調べて最小の距離を選ぶことができましたが、この方法ではアルゴリズムの実行時間はO(n 2 )になります。 もっと良い方法はありますか?


そのような問題に対する "標準的な"方法は、幾何学的実体のボロノイ図を構築することです。 これは時間O(N Log N)で行うことができます。

しかし、線分に対するそのようなダイアグラムの構築は困難であり、CGALのような既成の解決策に頼るべきです。





computational-geometry