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

9.5

 線分走査法

■

297

る。イベントキューは、シンプルな辞書式順序で整列したイベント点の平衡二分木

として表される。これによって、

y

値がより大きい点を最初にすることができる（走

査線はデカルト平面を上から下に走査する）。同じ

y

値の点では、

x

値が小さい方を

最初にする。

アルゴリズムのコードを単純化するために、走査線の状態を貯える二分木を、葉

の節点だけが実際の情報を含む強化平衡二分木にする。内部の節点は、左部分木

の最左線分と、右部分木の最右線分についての最小最大情報を貯える。木の中の

線分の順序は走査点、すなわち優先度付きキューから取り出されて現在処理中の

EventPoint

に基づいて行われる。

9.5.3

 解

例9-3に 示 した 解は、コードリポジトリ

JavaCode.src.algs.model.problems.

segmentIntersection

にあるクラス

EventPoint

,

EventQueue

,

LineState

に依存す

る。

例

9-3

 線分走査法の

Java

実装

public class LineSweep extends IntersectionDetection {

//

走査線状態とイベントキューを貯える

LineState lineState = new LineState();

EventQueue eq = new EventQueue();

//

線分配列からすべての線分の交点を計算する

public Hashtable<IPoint,ILineSegment[]>intersections ...