今回から平面走査法という手法による，線分の交差検出について解説します。この手法を使うことで，多数の線分の中から交点を高速に見つけ出すことができます。
はじめに
計算幾何学では，巨大な入力データを扱う可能性を想定して，計算量の少ない効率的なアルゴリズムの追求が行われます。今回からは，線分の集合から交差を検出する問題を取り上げます。平面走査法と呼ばれるアルゴリズムを使用することで，総当たり式の実装に比べ，計算量を大きく削減できることを見ていきます。
多数の線分から交差を見つける
前回，線分を表すLineSegmentクラスを作成し，2つの線分が交差するかどうかを調べるintersects()メソッドや，交点座標を求めるgetIntersectionPoint()メソッドを実装しました。
さて今後，プログラムの扱う線分が100個，1,000個，あるいはそれ以上に増えたときのことを考えてみましょう。これら多数の線分の中から交点を見つけ出すには，どうすれば良いでしょうか。それが今回のテーマです。
線分の交差を示すクラス
まず初めに，線分の交差を表現するクラスを作成しておきましょう。クラス名はIntersectionとし，交差する2つのLineSegmentオブジェクト，segment1とsegment2をフィールドに持たせます。
線分の交差を表現するクラス（Java）
public class Intersection {
public LineSegment segment1;
public LineSegment segment2;
public Intersection(LineSegment segment1, LineSegment segment2) {
this.segment1 = segment1;
this.segment2 = segment2;
}
public Point2D getIntersectionPoint() {
return segment1.getIntersectionPoint(segment2);
}
@Override
public String toString() {
return segment1 + " : " + segment2;
}
}
さて，今までLineクラスやLineSegmentクラスでは省略してきたequals()メソッドとhashCode()メソッドを，将来のプログラムの都合上，Intersectionクラスでは実装することにします。この2つは，オブジェクトの同値性判定に用いられる，きわめて重要なメソッドです。同値性とequals()，hashCode()の詳細については，[こちらの解説]などを参照してください。
ここでは，線分AとBからなるIntersectionオブジェクトと，線分BとAからなるIntersectionオブジェクトを同値とみなすことにします。すなわち，segment1フィールドとsegment2フィールドを交換しても同値性が保たれるように，equals()メソッドとhashCode()メソッドをオーバーライドします。実装は以下のようになります。
equals()メソッドとhashCode()メソッド（Java）
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
} else if (obj instanceof Intersection) {
Intersection other = (Intersection) obj;
// segment1とsegment2を交換しても同値性が変わらないようにする
if (segment1.equals(other.segment1) && segment2.equals(other.segment2)) {
return true;
} else if (segment1.equals(other.segment2) && segment2.equals(other.segment1)) {
return true;
}
}
return false;
}
@Override
public int hashCode() {
// segment1とsegment2を交換してもハッシュ値が変わらないようにする
return segment1.hashCode() + segment2.hashCode();
}
交差検出のインターフェース
次に，線分の交差検出を行うIntersectionDetectorインターフェースを作成しておきます。このインターフェースは，線分のリストを入力とし，その中から交差を見つけ，Intersectionオブジェクトのコレクションとして返すexecute()メソッドを持ちます。
IntersectionDetectorインターフェース（Java）
public interface IntersectionDetector {
Collection<Intersection> execute(List<LineSegment> segments);
}
