はじめに

前々回，前回と，平面走査法による線分交差検出について説明してきました。今回はその仕上げとして，いよいよ平面走査法のアルゴリズムの実装に挑戦します。

前回の復習

まず，前回導入した，平面走査法に必要な3つのデータ構造を復習しておきましょう。

• イベントは，線分の始点と終点，そして交点に対応するオブジェクトです。前回は，イベントを表現するEventクラスを作成しました。
• イベントキューは，イベントを要素とするコレクションです。キューの要素は，イベント点のy座標が小さい順に，常にソートされています。前回，イベントキューには，java.util.TreeSetクラスを利用することを説明しました。
• ステータスは，現在の走査線と交わる線分を要素とするコレクションです。ステータスの要素は，走査線と線分の交点のx座標が小さい順に，常にソートされています。ステータスにもTreeSetクラスを利用します。

この3つを使って交差検出のアルゴリズムを組み立てることが，今回のテーマになります。

イベントの処理

イベントキューには，未処理のイベント点が上から順番に格納されています。走査線を次のイベント点の位置まで動かす操作は，イベントキューから先頭の（最小のy座標を持つ）イベントを取り出す作業に対応します。

さて，こうしてイベントを取り出した後は，そのイベントに関してどんな処理を実行すれば良いのでしょうか。イベントの種類ごとに見ていきましょう。

始点イベントの処理

始点イベントをきっかけとして，その始点を持つ線分（S_startとします）は，走査線と交わり始めます。したがって，S_startをステータスに挿入する必要があります。

さらにこのとき，S_startと以下の線分の交差をチェックします。

• ステータス中でS_startの直前（左隣）に位置する線分（S_l）
• ステータス中でS_startの直後（右隣）に位置する線分（S_r）

もし交差する場合には，その交点イベントを新しく作成し，イベントキューに登録します。

図1は始点イベントの例です。この図の場合，S_startとS_rの交差が検出されます（赤い交点）。

交点イベントの処理

交点イベントには，交差する2つの線分が関わります。この2線分のうち，交点通過前の走査線上で左にあった線分をS'_l，右にあった線分をS'_rとします。

交点を境にして，S'_lとS'_rの走査線上の位置関係は逆転し，S'_lが右に，S'_rが左に来るようになります。したがって，ステータス上でのS'_lとS'_rの位置を入れ替える必要があります。

このとき，ステータスの線分の隣接関係が変化した部分に関して，以下の交差をチェックします。

• 元のステータス中でS'_lの直前（左隣）に位置した線分とS'_r
• 元のステータス中でS'_rの直後（右隣）に位置した線分とS'_l

それぞれ，交差する場合には，始点イベントでの交点検出時と同様に，交点イベントを作成してイベントキューに登録します（図2）。

終点イベントの処理

走査線が終点イベントに着くと，その終点を持つ線分（S_endとします）は，今後走査線と交わらなくなります。したがって，S_endをスタータスから削除する必要があります。

ここで，以下の線分を考えます。

• ステータス中でS_endの直前（左隣）に位置する線分（S''_l）
• ステータス中でS_endの直後（右隣）に位置する線分（S''_r）

S''_lとS''_rはこれまで，ステータス上で離れた位置にありました。しかし，S_endを削除したことによって，今後は隣接するようになります。したがって，このS''_lとS''_rの交差を新たにチェックし，交差する場合には交点イベントを作成・登録します（図3）。

以上をまとめると，表1のようになります。