the computational geometry algorithms library
分割統治:
1組の折れ線とそれらの軸合わせ最小境界ボックス間の最小距離(AAMBB)を表すデータ構造を定義します。pair
pair = (poly_a, poly_b, d_ab)
)距離
d_ab
をキーとして使用して、pair
データ構造用の空のキューを作成します。初期ポリラインを使用して
pair
データ構造を作成し、それをキューにプッシュします。これまでに見つかったポリライン間の最小距離(
min_d
)で変数を保持します。 無限大に設定してください。繰り返す:
最小距離
d_ab
要素をキューからポップします。d_ab
がd_ab
より大きい場合は終了です。ポリライン
poly_a
またはpoly_b
いずれかに唯一のセグメントが含まれる場合:- その間の最小距離を見つけるために総当たりを使用し、それに応じて
min_d
を更新します。
- その間の最小距離を見つけるために総当たりを使用し、それに応じて
さもないと:
ポリライン
poly_a
とpoly_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 。
そのような問題に対する "標準的な"方法は、幾何学的実体のボロノイ図を構築することです。 これは時間O(N Log N)で行うことができます。
しかし、線分に対するそのようなダイアグラムの構築は困難であり、CGALのような既成の解決策に頼るべきです。