読者です 読者をやめる 読者になる 読者になる

Panda Noir

JavaScript の限界を究めるブログです。

bentley-ottmannアルゴリズム

アルゴリズム

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

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

掃引線(SL)

sweep lineの訳です。平面上を左端から右端へと移動していく、y軸と並行な直線です。本記事では掃引線である直線SLが登場します。

データ構造

Bentley-Ottmann algorithmでは二種類のデータ構造を扱います。

ひとつはプライオリティーキューです。これは「イベント」を管理します。イベントというのは、「線分の左端点pとSLが交わる」「線分sと線分tの交点pとSLが交わる」「線分の右端点pとSLが交わる」の3種類があります。これらのイベントは点pのx座標により優先度がつけられます。

もうひとつは二分探索木です。掃引線Lと交わっている線分を管理します。これらの線分は、Lとの交点のy座標で優先度がつけられます。

アルゴリズム

  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の位置を交換します(掃引線Lとの交点を考えると、次から優先度が逆転するため)。交換後のsとtそれぞれのすぐ下の線分rs,rtとすぐ上の線分us,utを探します。rsかrtとsの交点、tとusまたはutの交点をイベントQから削除します。rsかrtとt、またはsとus、utが交差するなら、これらの交点をイベントとしてQに追加します。

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

アルゴリズム解説

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

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

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

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

備考

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

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

すぐ上の線分の求め方

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

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

すぐ下の線分の求め方

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

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

ほとんど同じです。

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