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のような既成の解決策に頼るべきです。