Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

bentley-ottmannアルゴリズム

約1ヶ月ぶりの更新です。いやー夏休み終わって部活再開してからめちゃくちゃ忙しくて大変です…

今回は、n本の線分の集合が与えられたとき、それらの交点をO(n log n)で求めるアルゴリズム、bentley-ottmannアルゴリズムを紹介します。実装はダラダラ進めているのでおまちください…

アルゴリズムの概要

bentley-ottmann アルゴリズムの基本方針は、「左端にy軸と並行な直線を一本引いて、その直線を左端から右端に動かしていく。いまその直線と交差している線分を管理しておいて、交差している線分同士が交差しているかを調べる」というものです。

y軸と並行で左端から右端へ動かす直線のことを掃引線(sweep line)と言うので、bentley-ottmann アルゴリズムは掃引線アルゴリズムの一種です。

アルゴリズム

  1. プライオリティーキューQを初期化します。初期のQは入力された線分の左端点、右端点に関するイベントを含んだ状態となります。
  2. 二分探索木Tを初期化します。初期のTは空です。
  3. Qが空になるまで、優先度が最小のイベントを取り出します。取り出したイベントの種類に応じて以下のとおりに処理します。
    1. イベントに関連付けられた点pが線分sの左端点ならば、線分sをTへ挿入します。Tの中で、線分sのすぐ下の線分rとすぐ上の線分tを取り出し、rとtの交点があるなら、この交点に関連付けられたイベントをQから削除します。もしsがrかtと交差するなら、交点をQにイベントとして追加します。
    2. 点pが線分sの右端点ならば、sのすぐ下の線分rとすぐ上の線分tを探し、sをTから削除します。rとtが交差するなら交点をQにイベントとして追加します。
    3. 点pが線分sと線分t(sは交点より左ではtの下である)の交点ならば、Tの中でのsとtの位置を交換します(掃引線との交点を考えると、次から優先度が逆転するため)。交換後のsとtそれぞれのすぐ下の線分rs,rtとすぐ上の線分us,utを探します。rsかrtとsの交点、tとusまたはutの交点をイベントQから削除します。rsかrtとt、またはsとus、utが交差するなら、これらの交点をイベントとしてQに追加します。

おおすじはwikiの和訳ですが、一部表現を削ったり足したりしてわかりやすくしてあります。

アルゴリズム解説

このアルゴリズムでは、「掃引線を左端から走らせ、掃引線と交差した線分のみを見ることで、効率よく交点を探す」という戦略が基本となっています。

掃引線は左端からスムーズに途切れなく動かす必要はありません。効率よく探すことが大切なので、「線分の左端にたどり着いた」「線分と線分の交点にたどり着いた」「線分の右端にたどり着いた」この3つのいずれかが起こるところへジャンプしながら進むだけでOKです。

「線分の左(右)端にたどり着いた」イベントは、現在掃引線と交差している線分を把握するため必要です。では、「線分と線分の交点にたどり着いた」こちらはなぜ必要なのでしょうか?

これは、線分と掃引線の交点を扱いやすくするためです。線分は掃引線との交点のy座標順にソートされ、二分探索木にて管理されます。掃引線を動かせば、線分と掃引線の交点は変化します。しかし、大小関係は線分が交差しないかぎり変わりません*1。だから、大小関係が前後してしまう交点でのイベントを扱わねばなりません。

備考

アルゴリズム中で、Tの中でsのすぐ上、すぐ下の線分を求める必要が出てきます。

すぐ上の線分というのは、sと掃引線の交点のy座標より、掃引線との交点のy座標が大きいものの中で最小となる線分、のことです。…ややこしいですね。要するに図的にみたとき、掃引線と交わっている線分のうちsのすぐ上にあるもののことです。

すぐ上の線分の求め方

根ノードを最初の着目ノードとします。

  1. 着目ノードがsより大きいなら、これを暫定的にすぐ上の線分として、このノードの左の子を次の着目ノードとします。
  2. 着目ノードがsより小さいか等しいなら、右の子を次の着目ノードとします。
  3. 着目ノードがないならば、暫定的に定めていた線分をすぐ上の線分として返します。

すぐ下の線分の求め方

根ノードを最初の着目ノードとします。

  1. 着目ノードがsより大きいか等しいなら、このノードの左の子を次の着目ノードとします。
  2. 着目ノードがsより小さいなら、これを暫定的にすぐ下の線分として、右の子を次の着目ノードとします。
  3. 着目ノードがないならば、暫定的に定めていた線分をすぐ下の線分として返します。

ほとんど同じです。

*1:大小関係さえ管理できれば、このアルゴリズムではy座標が変わっても問題はありません