交点--幾何学的に線分の交点を判断する問題

0x01.に質問
2つの線分(始点start = {X1, Y1}と終点end = {X2, Y2}として表される)を指定し、交点がある場合はその交点を計算し、交点がない場合は空の値を返します.浮動小数点型誤差は10^-6を超えません.複数の交点がある場合は(線分が重なる)はX値が最も小さい点、X座標が同じであればY値が最も小さい点を返します.座標の絶対値は2^7を超えず、入力した座標はいずれも有効な2次元座標です.
入力例:line 1={0,0},{3,3}line 2={1,1},{2,2}出力例:{1,1}
『プログラマー面接金典』16.03より

public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2)

0x02.簡単な分析
初めて見ると、数学の幾何学の問題で、難易度が低いと思っていたが、よく考えてみると、直線の交点ではなく、線分の交点であることが分かった.具体的な考え方は以下の通りです.

は、2つの線分が位置する直線が平行であるか否かを先に判断する(傾きで判断する).

平行であれば、直線が重なるかどうかを考慮します.

重ならなければ、交点はないに違いない.

が重なると、各直線の端点が別の直線上の線分上にあるかどうかを順次判断し、交点を最小値に更新し続ける.

が平行でなければ、パラメータ方程式を用いてパラメータt1とt2を算出し、t1,t2が[0,1]に属するかどうかを判断して交点があり、交点を算出し、属さなければ交点がない.

0x03.解決コード–分類ディスカッション

class Solution {
    private boolean inside(int x1,int y1,int x2,int y2,int x,int y){
        //     x ，y   ，    
        return (x1 == x2 || (Math.min(x1, x2) <= x && x <= Math.max(x1, x2))) 
        && (y1 == y2 || (Math.min(y1, y2) <= y && y <= Math.max(y1, y2)));
    }
    private void up(double[]result,double x,double y){
        if((result[0]==Integer.MAX_VALUE)||x<result[0]||(x==result[0]&&y<result[1])){
            result[0]=x;
            result[1]=y;
        }
    }
    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
        int x1=start1[0],y1=start1[1];
        int x2=end1[0],y2=end1[1];
        int x3=start2[0],y3=start2[1];
        int x4=end2[0],y4=end2[1];
        double[] result=new double[2];
        result[0]=Integer.MAX_VALUE;
        result[1]=Integer.MAX_VALUE;
        //    
        if ((y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3)) {
             //         
            if ((y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)){
                //   (x3, y3)    「  」(x1, y1)~(x2, y2)  
                if (inside(x1, y1, x2, y2, x3, y3)) {
                    up(result,(double)x3,(double)y3);
                }
                 //    (x4, y4)    「  」(x1, y1)~(x2, y2)  
                 if (inside(x1, y1, x2, y2, x4, y4)) {
                    up(result, (double)x4, (double)y4);
                }
                //    (x1, y1)    「  」(x3, y3)~(x4, y4)  
                if (inside(x3, y3, x4, y4, x1, y1)) {
                    up(result, (double)x1, (double)y1);
                }
                //    (x2, y2)    「  」(x3, y3)~(x4, y4)  
                if (inside(x3, y3, x4, y4, x2, y2)) {
                    up(result, (double)x2, (double)y2);
                }    
            }
        }else{
            //      
            double t1 = (double)(x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3)
             - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));
            double t2 = (double)(x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1)
             - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3));
            //          [0,1]
            if (t1 >= 0.0 && t1 <= 1.0 && t2 >= 0.0 && t2 <= 1.0) {
                result[0] = x1 + t1 * (x2 - x1);
                result[1] = y1+  t1 * (y2 - y1);
            }
        }
        return result[0]==Integer.MAX_VALUE?new double[]{}:result;
    }
}

私は山を越えて、水を渡って、万物が蘇るのを見たことがあります.水は__で、万物は_です.心の中は少し清明で、やはり_.
ATFWUS --Writing By 2020–04-12