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

9.5

 線分走査法

■

295

者は隣り合わねばならない。実際、

線分走査法

は、この線分の状態を管理して、効

率的に交点を見つける。

図9-7で示した

9

つの水平走査線の位置をよく見ると、これらが

(i)

線分の始点ま

たは終点、あるいは

(ii)

交点の場所で選ばれていることがわかるだろう。

線分走査

法

は、実際にデカルト平面上を「走査」するのではない。ただ、イベントキューに

2*n

個の線分端点を挿入するだけである。このイベントキューは、優先度付きキュー

に修正を加えたものだ。線分の始終点を含めたすべての存在する交点が、これらの

キューに入った点の処理によって検出できる。

線分走査法

は、このキューを処理す

ることで、走査線

L

の状態を構築し、隣り合う線分がいつ交差するか決定する。

9.5.1

 入出力

線分走査法

は、デカルト平面上の

n

個の線分の集合

S

を処理する。

S

には重複した

線分は存在しない。どの線分も共線（すなわち、同じ角度で互いに重なる）にはな

い。

アルゴリズムは、水平および垂直の線分を扱えるが、線分の順序付けと計算には注

意を要する。どの線分も一点に縮退する（すなわち、線分の始点と終点が同じにな

る）ことはない。

出力は、線分間の交点（存在する場合）を表す

k

個の点の集合、およびその各点

p

i

について、交点を形成する線分となる。

9.5.2

 文脈

交点の期待個数が、線分の個数に比べて大幅に少ない場合には、

線分走査法

は力

任せの方式に比べて、優れた性能を示す。交点の個数が多い場合には、保守処理の

手間がかかり便益を打ち消してし ...