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

294

■

9

章 計算幾何学

9.5

 線分走査法

幾何学的形の間の交差を見つけなければならないという状況は多数存在する。

VLSI

チップの設計では、回路を基板に描画するのだが、予期しない交差があって

はならない。旅行計画では、道を線分としてデータベースに貯え、交差点を線分の

間の交点として決定する。

図9-7では、

6

つの線分間の

7

つの交点の例を示す。すべての可能な組み合わせ

である

C(n, 2)

、すなわち

n*(n

−

1)/2

個の線分を比較する必要はないだろう。結

局、明らかに離れている線分（この例では、

S

1

と

S

4

）は交差できない。

線分走査法

（

LineSweep

）は、処理中に入力要素の部分集合に注目することによって、効率を改

善するというよく知られた方式を用いる。線分の入力集合の上から下まで、水平方

向の線

L

で走査して、

L

によって見つかった交点を報告する。図9-7は、上から下ま

での走査における

L

の状態を（

9

つの位置について）示す。

線分走査法状態 報告される交点

を報告

を報告

 を報告

を報告

を報告

図9-7　6 つの線分から 7つの交点を検出する

線分走査法

の革新的なところは、

y

座標を固定して線分を左から右へと順に認識

することである。水平な線分は、左端の点が右端の点より「高い」位置にあるとして

処理される。線分の交差は、各瞬間の走査線上で隣り合う線分間でのみ生じる。具

体的には、

2

つの線分

S

i

と

S

j

とが交差するとき、線分走査の途中のある瞬間で、両