はじめに

今回からは、 前回作成した直線クラスをもとに、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) || (t1 >= 0 && t2 

上のコードの不等式判定は、もっと簡略化できます。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 

線分同士の交差判定

※

以下で解説しているアルゴリズムには、特別な状況で正しく動作しない問題がありました。詳細は「第7回　（⁠臨時回）線分の交差判定再訪⁠）⁠」を参照してください。

次に、LineSegmentオブジェクト同士の交差を判定する方法を考えてみましょう。やや複雑に思えますが、線分と直線の交差判定を応用することで解決できます。

図5のように、線分s1とs2があるとします。s1を延長して直線l1を、s2を延長して直線l2を作ります。このとき、s1がl2と交差し、かつs2とl1が交差するのであれば、s1とs2も交差することになります。実際、図5ではこの条件が成立し、s1とs2は交差しています。

一方、図5でs1とs3（およびl1とl3）の関係を見てみると、s1とl3は交差しているものの、s3とl1は交差していません。このような場合、s1とs3は交差しないことになります。

以上を踏まえて、線分を引数にとるバージョンのintersects()メソッドを記述すると、次のようになります。

public boolean intersects(LineSegment s) {
    return intersects(s.toLine()) && s.intersects(toLine());
}

線分と直線、線分同士の交点座標

線分と直線、あるいは線分同士が交差するかどうかを判定できるようになったので、さらに、それらが交差する場合の交点座標を求めてみましょう。これは非常に簡単です。というのも、線分を延長して直線化することで、直線同士の交点座標を求める問題に帰着することができるからです。直線同士の交点座標は、前回のLineクラスで作成したgetIntersectionPoint()メソッドで解決済みです。

この方針に基づいて、LineSegmentクラスにgetIntersectionPoint()メソッドを追加してみましょう。ただし、線分が交差しない場合はnullを返すものとします。

public Point2D getIntersectionPoint(Line l) {
    if (!intersects(l)) {
        return null; // 交差しない場合はnullを返す
    }
    return l.getIntersectionPoint(toLine());
}

public Point2D getIntersectionPoint(LineSegment s) {
    if (!intersects(s)) {
        return null; // 交差しない場合はnullを返す
    }
    return s.toLine().getIntersectionPoint(toLine());
}

動作確認

今回実装した線分の交差判定をグラフィカルに動作確認できるよう、Swingアプリケーションのデモプログラムを用意しました。Java Web Start形式になっており、 こちらをクリックして直接起動できます。ソースコードはここには掲載しませんので、アーカイブを下記入手先URLよりダウンロードして確認してください。

デモプログラムを起動すると、画面に2つの線分が表示されます。線分の端点をマウスでドラッグすると、端点を移動することができます。線分が交差する場合には、その交点が赤く表示されます。

まとめと次回予告

今回は、線分クラスを作成し、線分と直線、そして線分同士の交差判定の問題を取り上げました。第1回で作成済みの直線クラスを活用することで、簡潔な実装を行うことができました。

今回作成したプログラムとデモ用のSwingアプリケーションのソースコードは、こちらからダウンロードできます。

次回からは、いよいよ本格的な計算幾何の世界に入っていきます。お楽しみに！