matlab判断点在线段上_线段交点-LeetCode面试题 16.03-困难-C#

小灰灰 2023-01-01 08:57 95阅读 0赞

## 题目 ##

线段交点leetcode-cn.com

给定两条线段（表示为起点start = \{X1, Y1\}和终点end = \{X2, Y2\}），如果它们有交点，请计算其交点，没有交点则返回空值。

要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

示例 1：
    输入：
    line1 = {0, 0}, {1, 0}
    line2 = {1, 1}, {0, -1}
    输出： {0.5, 0}
    示例 2：
    输入：
    line1 = {0, 0}, {3, 3}
    line2 = {1, 1}, {2, 2}
    输出： {1, 1}
    示例 3：
    输入：
    line1 = {0, 0}, {1, 1}
    line2 = {1, 0}, {2, 1}
    输出： {}，两条线段没有交点
    提示：
        坐标绝对值不会超过 2^7
        输入的坐标均是有效的二维坐标

## 解析 ##

1.  根据斜率判断(y2-y1)/(x2-x1) = (y4-y3)/(x4-x3)
2.  //判断是否在一条直线上：数学斜率计算 (y3-y1)/(x3-x1) = (y2-y1)/(x2-x1)
    
    1.  如果在一条直线上，则判断一条线段上的每个点在不在另一个线段上，判断方法如下：
    2.  //如果x1 == x2则只需判断y，若y1 == y2 则则只需判断x  
        (x1 == x2||(Math.Max(x1, x2) >= x && Math.Min(x1, x2) <= x))&& (y1 == y2||(Math.Max(y1, y2) >= y && Math.Min(y1, y2) <= y))
3.  不在一条直线上时，则需要借助方程的一般表达式进行计算
    
    1.  //一般方程式推导：
        
        1.  线段1，相交点(x,y)： x = x1+(x2-x1)\*t1 y = y1+(y2-y1)\*t1
        2.  线段2，相交点(x,y)：x = x3+(x4-x3)\*t2 y = y3+(y4-y3)\*t2

![ba88fe6f62a692940635c42ba8a93fac.png][]

1.  1.  //两个方程联立得到  
        x1+(x2-x1)\*t1 = x3+(x4-x3)\*t2 y1+(y2-y1)\*t1 = y3+(y4-y3)\*t2
    2.  求出t1和t2,判断t1和t2是否满足大于等于0且小于1的条件，若满足直接计算交点，不满足返回空

## 代码 ##

public class Solution {
         
     public double[] Intersection(int[] start1, int[] end1, int[] start2, int[] end2)
        {
         
            double[] res = new Double[2] {
         double.MaxValue, double.MaxValue};
            int x1 = start1[0], x2 = end1[0], y1 = start1[1], y2 = end1[1];
            int x3 = start2[0], x4 = end2[0], y3 = start2[1], y4 = end2[1];
            //数学斜率计算  △y1/△x1 = △y2/△x2
            //(y2-y1)/(x2-x1) = (y4-y3)/(x4-x3)
            //平行
            if ((y2 - y1) * (x4 - x3) == (y4 - y3) * (x2 - x1))
            {
         
                //判断是否在一条直线上
                //数学斜率计算 (y3-y1)/(x3-x1) = (y2-y1)/(x2-x1)
                if ((y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1))
                {
         
                    //判断四种点在线段上
                    if (IsOverLerp(x1, y1, x2, y2, x3, y3))
                    {
         
                        OverLerp(res, x3, y3);
                    }
    
                    if (IsOverLerp(x1, y1, x2, y2, x4, y4))
                    {
         
                        OverLerp(res, x4, y4);
                    }
    
                    if (IsOverLerp(x3, y3, x4, y4, x1, y1))
                    {
         
                        OverLerp(res, x1, y1);
                    }
    
                    if (IsOverLerp(x3, y3, x4, y4, x2, y2))
                    {
         
                        OverLerp(res, x1, y2);
                    }
                }
            }
            else
            {
         
                //一般方程式推导
                //线段1，相交点(x,y)
                // x = x1+(x2-x1)*t1   y = y1+(y2-y1)*t1
    
                //线段2，相交点(x,y)
                // x = x3+(x4-x3)*t2   y = y3+(y4-y3)*t2
                //两个方程联立得到
                //x1+(x2-x1)*t1 = x3+(x4-x3)*t2    y1+(y2-y1)*t1 = y3+(y4-y3)*t2
                // (x1+(x2-x1)*t1-x3)/(x4-x3) = (y1+(y2-y1)*t1 -y3)/(y4-y3)
                double t1 = (double) ((x4 - x3) * (y1 - y3) - (x1 - x3) * (y4 - y3)) /
                            ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));
                double t2 = (double) ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) /
                            ((y2 - y1) * (x4 - x3) - (x2 - x1) * (y4 - y3));
                if (t1 >= 0.0 && t1 <= 1.0 && t2 >= 0.0 && t2 <= 1.0)
                {
         
                    res[0] = x1 + (x2 - x1) * t1;
                    res[1] = y1 + (y2 - y1) * t1;
                }
            }
    
            return double.MaxValue == res[0] ? new double[0] : res;
        }
    
        /// <summary>
        /// 更新重叠
        /// </summary>
        void OverLerp(double[] res, double x, double y)
        {
         
            if (res[0] > x || (x == res[0] && res[1] > y))
            {
         
                res[0] = x;
                res[1] = y;
            }
        }
    
        /// <summary>
        /// 是否重叠，前提是已经在一条直线上
        /// <param name="x1"></param>
        /// <param name="y1"></param>
        /// <param name="x2"></param>
        /// <param name="y2"></param>
        /// <param name="x">要判断的点x</param>
        /// <param name="y">要判断的点y</param>
        /// <returns></returns>
        ///  </summary>
        bool IsOverLerp(int x1, int y1, int x2, int y2, int x, int y)
        {
         
            //如果x1 == x2或者y1 == y2 则肯定是相交的
            return (x1 == x2||(Math.Max(x1, x2) >= x && Math.Min(x1, x2) <= x))&& (y1 == y2||(Math.Max(y1, y2) >= y && Math.Min(y1, y2) <= y));
            
        }
    }

[ba88fe6f62a692940635c42ba8a93fac.png]: /images/20221120/465dc1c5bdef486a87f718f79a73f36f.png