はじめに

今回は，平面走査法による線分交差検出のデータ構造を実装していきます。内容がかなり難しくなってきますが，説明とソースコードを納得できるまで読み返していただければと思います。

平面走査法と水平方向

前回は，多数の線分から交差を検出する方法として，平面走査法（plane sweep algorithm）の考え方を紹介しました。これは，x軸に平行な走査線を上から下へと動かしていき，走査線と交わる線分のみを計算対象とすることで，交差検出の計算量を減らすというものでした（図1）。

実は，これだけでは考え方としてまだ不足なのです。図2を見てください。図2では図1と違い，すべての線分が同じくらいのy座標範囲にまとまって存在しています。こうした場合，走査線が多数の線分と交わる時間が大半を占めるため，計算量をほとんど削減できないことになってしまいます。

この状況を改善するには，走査線で垂直方向の計算範囲を限定することに加えて，水平方向にも計算の局所性を持たせる必要があります。具体的には，走査線と線分の交点のx座標を基準にして，水平方向に隣接した線分同士の交差のみをチェックするのです。この様子を図3に示します。

平面走査法のデータ構造

以上が，平面走査法による線分交差検出の概要です。このアルゴリズムを実装していくわけですが，まず初めに，アルゴリズムで用いるデータ構造を3つ導入します。3つのデータ構造とは，イベント，イベントキュー，そしてステータスです。

なお，今回からは図4のように，y座標が上から下に向かって増加する座標系を採用します。

イベント

走査線は上から下まで動かすと先に述べました。しかし，実際のアルゴリズムでは連続的に動かすわけではなく，特定のイベント点を単位として，離散的に位置を変化させることになります。

イベント点になるのは，アルゴリズムの入力となるすべての線分の端点，そして，計算途中で検出された線分同士の交点です。計算の開始時点では，線分の端点に対応するイベントのみが存在しますが，走査線が移動し，新たな交点が見つかるたびに，交点に対応するイベントが生成されていきます。

イベントオブジェクトは，そのイベント点の座標と，点の種類（線分の始点，線分の終点，線分同士の交点のいずれか）を保持します。さらに，点に関連する線分（始点または終点イベントの場合はその線分，交点イベントの場合は交差する2線分）も合わせて保持します。

イベントキュー

イベントキューは，イベントの順序付き集合です。ここでの順序は，イベントのy座標の大小関係にもとづいて定義され，イベントキューの先頭位置にあるイベントはキューの中で最小のy座標を持ちます。走査線を現在の位置から次の位置へと移動する処理は，イベントキューから先頭のイベントを取り出す作業に相当します。

ステータス

ステータスは，現在の走査線と交差するすべての線分の順序付き集合です。ここでの順序は，走査線と各線分の交点のx座標の大小関係にもとづいて定義されます。この順序関係は，走査線の移動にともなって動的に変化します。例えば，図5で走査線が(A)の位置にあるとき，ステータスは(s1, s2, s3, s4)の順序を保持していますが，走査線が(B)まで下がると，順序は(s1, s3, s2, s4)に変化します。