はじめに
前々回,
前回の復習
まず,
- イベントは,
線分の始点と終点, そして交点に対応するオブジェクトです。前回は, イベントを表現するEventクラスを作成しました。 - イベントキューは,
イベントを要素とするコレクションです。キューの要素は, イベント点のy座標が小さい順に, 常にソートされています。前回, イベントキューには, java. util. TreeSetクラスを利用することを説明しました。 - ステータスは,
現在の走査線と交わる線分を要素とするコレクションです。ステータスの要素は, 走査線と線分の交点のx座標が小さい順に, 常にソートされています。ステータスにもTreeSetクラスを利用します。
この3つを使って交差検出のアルゴリズムを組み立てることが,
イベントの処理
イベントキューには,
さて,
始点イベントの処理
始点イベントをきっかけとして,
さらにこのとき,
- ステータス中でSstartの直前
(左隣) に位置する線分 (Sl) - ステータス中でSstartの直後
(右隣) に位置する線分 (Sr)
もし交差する場合には,
図1は始点イベントの例です。この図の場合,
交点イベントの処理
交点イベントには,
交点を境にして,
このとき,
- 元のステータス中でS'lの直前
(左隣) に位置した線分とS'r - 元のステータス中でS'rの直後
(右隣) に位置した線分とS'l
それぞれ,
終点イベントの処理
走査線が終点イベントに着くと,
ここで,
- ステータス中でSendの直前
(左隣) に位置する線分 (S''l) - ステータス中でSendの直後
(右隣) に位置する線分 (S''r)
S''lとS''rはこれまで,
以上をまとめると,
表1 イベントの処理
種類 | ステータスの変更 | 交差チェック対象 |
---|---|---|
始点 | 線分を挿入 | 挿入した線分とその左隣/ |
交点 | 2線分の位置を交換 | 新しく左に来る線分とその左隣/ |
終点 | 線分を削除 | 削除する線分の左隣と右隣 |