【Java】2つの線分の交点を求める

f:id:shogonir:20171227012618p:plain

 

目次

  1. この記事の目的
  2. x, y-平面上の線分を表すクラス
  3. 2つの線分の交点をもとめる方法
  4. まとめ

 

1. この記事の目的

この記事では2つの線分の交点を求める方法を紹介します。
そのために必要になる、線分を表すクラスのコードも紹介します。

サンプルコードを上げました。

github.com

 

2. x, y-平面上の線分を表すクラス

線分を表すクラスを実装します。
とはいっても、今回はほとんどメソッドを実装する必要はありません。

 

package model;

/**
 * Created by shogo on 2017/11/30.
 */
public class Line2 {

    private Point2 s;
    private Point2 t;

    public Line2(Point2 s, Point2 t) {
        this.s = s;
        this.t = t;
    }

    public Point2 getS() {
        return this.s;
    }

    public Point2 getT() {
        return this.t;
    }
}

 

2次元平面上の線分を表すクラスは、2つの点をメンバとしてもちます。
コンストラクタで2つの点をセットします。
また、getterを実装して始点と端点を取得できるようにします。

このクラスについての説明は以上です。
早速、線分の交点を求めるソースコードを紹介します。

 

3. 2つの線分の交点をもとめる方法

線分の交点を求める方法について、ソースコードは以下の通りになります。

 

    public static boolean lineIntersection(Line2 l1, Line2 l2, Point2 intersection, boolean includesEndPoints) {
        if (!lineIntersects(l1, l2, includesEndPoints)) {
            intersection = null;
            return false;
        }

        double ax = l1.getS().getX();
        double ay = l1.getS().getY();
        double bx = l1.getT().getX();
        double by = l1.getT().getY();
        double cx = l2.getS().getX();
        double cy = l2.getS().getY();
        double dx = l2.getT().getX();
        double dy = l2.getT().getY();
        double d = (bx - ax) * (dy - cy) - (by - ay) * (dx - cx);
        double u = ((cx - ax) * (dy - cy) - (cy - ay) * (dx - cx)) / d;
        double v = ((cx - ax) * (by - ay) - (cy - ay) * (bx - ax)) / d;

        if ((!includesEndPoints && (u <= 0 || u >= 1 || v <= 0 || v >= 1)) ||
                (includesEndPoints && (u < 0 || u > 1 || v < 0 || v > 1))) {
            intersection = null;
            return false;
        }

        double x = ax + u * (bx - ax);
        double y = ay + u * (by - ay);
        intersection.set(x, y);
        return true;
    }

 

このコードで大事なのは変数uとvです。
線分1の始点と端点をそれぞれaとb、線分2の始点と端点をそれぞれcとdとしています。
そして、uとvはそれぞれ交点までの内分の比率になっています。
なので最後にxとyを求める際には、uを使ってvは使っていません。

 

最後にデフォルト引数の実装を行います。
線分の交点を求める際に、線分の端点を含むかどうかの引数includesEndPointsですが、普段はfalseで呼ぶことが多いです。
なのでデフォルトでfalseになるように実装します。

 

    public static boolean lineIntersection(Line2 l1, Line2 l2, Point2 intersection) {
        return lineIntersection(l1, l2, intersection, false);
    }

 

Javaは言語レベルでデフォルト引数をサポートしていませんので、オーバーロードを使いました。

 

4. まとめ

今回は線分の交点を求める方法を紹介しました。
実装してから思いましたが、booleanではなく交点を返すI/Fにしてもよかったですね。
交点がない場合はnullを返すとかで。