アルゴリズムクイックリファレンス 第2版

300

■

9

章 計算幾何学

分としてのみ貯え、その後で、

S

4

を交差線分として追加で貯える。より複雑な例で、

線分

S

2

と

S

5

との交点を表すイベント点が優先度付きキューに挿入されるときは、追

加情報には何も貯えられない。しかし、このイベント点の処理後は、交差線分とし

て、

S

6

, S

2

, S

5

を貯える。

線分走査法

の計算の中心はクラス

LineState

である。

LineState

は、平面上で、上

から下へと走査するときに、現在の走査点を管理する。

EventQueue

から、最小デー

タを取り出したときに、比較子

pointSorter

は、上から下の順に、または左から右

の順に、

EventPoint

オブジェクトを適切に返す。

線分走査法

の本当の仕事は、

LineState

の

determineIntersecting

メソッドの中

にある。leftとrightの間にある線分を反復処理することによって交差が決定され

る。このような支援クラスの詳細は、本書に付

随するコードリポジトリ、例えば

LineState.java

からわかる。

線分走査法

は、走査点を進めていくときに、処理中の線分を再整列できるので、

O((n

＋

k) log n)

性能を達成する。この処理に、

s

をその状態にある線分の個数とし

て、

O(log s)

より多くの手順が必要なら、アルゴリズム全体の性能は、

O(n

2

)

まで

低下する。例えば、線分状態を単純に二重リンク付きリスト（迅速に前の線分と次

の線分を見つけるには有用な構造）で貯えるなら、挿入操作は、リスト内の線分を ...