交点--几何判断线段交点问题

0x01.问题

给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。
要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。
坐标绝对值不会超过 2^7，输入的坐标均是有效的二维坐标。

输入示例：
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
输出示例：
{1, 1}

来自《程序员面试金典》16.03

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

0x02.简要分析

初看，是个数学的几何问题，以为难度不大，后来仔细一想，发现不是直线的交点，是线段的交点，那么需要考虑的特殊情况就有些多，不过只要理清思路，还是不难的。
具体思路如下：

• 先判断两条线段所在直线是否平行（用斜率判断）。

  • 如果平行，再考虑所在直线是否重合。

    • 如果不重合，一定没有交点。

    • 如果重合，那么依次判断每个直线的端点是否在另一条直线上线段上，并不断更新交点为最小值。

  • 如果不平行，那么使用参数方程算出参数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