はじめに

今回からは， 前回作成した直線クラスをもとに，2次元平面上の2点を結ぶ線分について考えていきます。線分は直線の一部ですが，現実のアプリケーションでは，直線よりも線分を扱うケースの方が多くなります。なぜなら，線分の集合を使って，さまざまな図形を表現できるからです。Blogopolisでは，図1に示すように土地の各区画が多角形で構成されていますが，これらの多角形も，内部的には線分の組み合わせになっています。

今回は線分を表すクラスを作成し，直線や他の線分との交差判定を実装することにします。

線分クラス

では早速，2次元平面上の線分を示すLineSegmentクラスを作ってみましょう。LineSegmentクラスは，端点の座標(x1, y1)と(x2, y2)をフィールドとして保持します。

public class LineSegment {
    public double x1;
    public double y1;
    public double x2;
    public double y2;

    public LineSegment(double x1, double y1, double x2, double y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }

    @Override
    public String toString() {
        return "(" + x1 + ", " + y1 + ") - (" + x2 + ", " + y2 + ")";
    }
}

さて，線分を永遠に延長すると直線になります（図2）。この直線への変換を行うtoLine()メソッドを，LineSegmentクラス内に用意しておくことにします。直線の表現には，前回作成したLineクラスをそのまま使用します。

public Line toLine() {
    return Line.fromPoints(x1, y1, x2, y2);
}

線分と直線の交差判定

2つの直線は，平行でない限り必ず交わります。これに対して，線分と直線は図3のように，交差する場合もあれば交差しない場合もあります。どのような条件がみたされたとき，線分と直線が交差するのかを調べてみましょう。

なお，今回の連載では，線分の端点がちょうど直線上に重なる場合も「交差」するものとします。

以下の直線の方程式を考えます。

この式の等号を不等号に変えることで，2次元平面を式(1)の直線で2つに区切ったときの一方となる半平面（half plane）を示す式(2)が得られます。また，不等号の向きを逆にすると，式(2)のもう一方となる反対側の半平面を示す式(3)が得られます。この様子を図4に示します。

図4を見ると，線分と直線が交差する，つまり線分が直線を「またぐ」のは，線分の2つの端点が互いに異なる半平面の上にあるときであることが分かります。これは，線分の端点の一方が式(2)をみたし，もう一方が式(3)をみたす場合にあたります。

これを実装してみましょう。LineSegmentクラスに，引数で与えられた直線と交差するかどうかを判定するintersects()メソッドを追加します。

public boolean intersects(Line l) {
    double t1 = l.a * x1 + l.b * y1 + l.c; // 端点1の座標を直線の式に代入
    double t2 = l.a * x2 + l.b * y2 + l.c; // 端点2の座標を直線の式に代入
    return (t1 <= 0 && t2 >= 0) || (t1 >= 0 && t2 <= 0); // 不等式の判定
}

上のコードの不等式判定は，もっと簡略化できます。t1とt2の積をとって，その正負を調べれば良いのです。この改良を加えたコードを以下に示します。

public boolean intersects(Line l) {
    double t1 = l.a * x1 + l.b * y1 + l.c;
    double t2 = l.a * x2 + l.b * y2 + l.c;
    return t1 * t2 <= 0; // 上の判定と等価
}