線分と線分の交差判定と交点座標

線分と線分が交差するかどうかを判定する

線分の交差判定アルゴリズムは記事[1]に詳しい。幸い、Java には交差判定メソッドが提供されている[2]。

static boolean  linesIntersect(double X1, double Y1, double X2, double Y2, double X3, double Y3, double X4, double Y4)

(X1, Y1) から (X2, Y2) までの線分が (X3, Y3) から (X4, Y4) までの線分と交差するかどうかを判定する。

接している場合も交差有りとなるかどうかは、マニュアルでははっきりしない。実際にプログラムを書いて確かめる。

線分と線分の交点座標を求める

交差するとき、交点の座標は次のようにして求められる。

    void getIntersection(float X0, float Y0, float X1, float Y1,
              float X2, float Y2, float X3, float Y3, float[] center) {
        float S1 = ((X3 - X2) * (Y0 - Y2) - (Y3 - Y2) * (X0 - X2)) / 2;
        float S2 = ((X3 - X2) * (Y2 - Y1) - (Y3 - Y2) * (X2 - X1)) / 2;
        center[0] = X0 + (X1 - X0) * S1 / (S1 + S2);
        center[1] = Y0 + (Y1 - Y0) * S1 / (S1 + S2);
    }

(X2,Y2) - (X3,Y3) が水平線の場合

Y2 == Y3 であるから

    S1 = (X3 - X2) * (Y0 - Y2) / 2;
    S1 + S2 = (X3 - X2) * (Y0 - Y1) /2;
    X = X0 + (X1 - X0) * (Y2 - Y0) / (Y1 - Y0);
    Y = Y2;

(X2,Y2) - (X3,Y3) が垂直線の場合

X2 == X3 であるから

   S1 = ( - (Y3 - Y2) * (X0 - X2)) / 2;
   S2 = ( - (Y3 - Y2) * (X2 - X1)) / 2;
   S1 + S2 = ( - (Y3 - Y2) * (X0 - X1)) / 2;
   S1/(S1 + S2) = (X0 - X2) / (X0 - X1);

   X = X2;
   Y = Y0 + (Y1 - Y0) * (X2 - X0) / (X1 - X0);

参考記事