题目描述

给定两条线段（表示为起点 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
输入的坐标均是有效的二维坐标

题目思考

如何简化问题?
可以利用哪些数学/几何知识?

解决方案

思路

分析题目, 首先我们可以想到的是求对应直线的交点, 然后检查交点是否落在线段上即可
根据线段两个端点, 我们可以得到对应直线的斜截式, 这里特别需要注意的是平行于 y 轴的情况, 此时斜率不存在
然后分析两直线的关系, 这里可以分为平行不共线/共线/相交三种情况:
1. 平行不共线时显然没有交点
2. 共线时需要返回 x/y 值最小的交点, 显然这个点一定属于两条线段的四个端点之一, 我们只需要遍历这四个端点, 检查其是否同时位于两个线段内, 然后最小的满足条件的点即可
3. 相交时只有唯一一个交点, 我们可以联立两个斜截式得到对应交点, 然后检查其是否同时位于两个线段内即可
下面代码就对应了上面的整个过程, 且每一步有详细的注释, 方便大家理解

复杂度

时间复杂度 O(1): 只需要进行常数次计算
空间复杂度 O(1): 只使用了几个常数空间变量

代码

class Solution:
    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
        # 计算线段对应直线的斜截式+分四种情况+有效交点列表+注意浮点数误差
        # ep表示题目要求的浮点数精度误差
        ep = 1e-6

        def getKB(start, end):
            # 给定线段(start, end), 得到其对应直线的斜率k和截距b
            x1, y1 = start
            x2, y2 = end
            if x1 == x2:
                # 平行于y轴的情况, 斜率是inf
                return float("inf"), x1
            return (y1 - y2) / (x1 - x2), (x1 * y2 - x2 * y1) / (x1 - x2)

        def equal(a, b):
            # 注意浮点数计算有精度误差, 所以需要额外equal函数
            # 由于a和b可能是inf, 而inf的差的绝对值不满足小于等于1e-6, 所以需要额外等于比较
            return a == b or abs(a - b) <= ep

        def isInside(x, y, start, end):
            # 检查给定点(x,y)是否在线段(start, end)内
            x1, y1 = start
            x2, y2 = end
            # 注意这里的比较也需要考虑浮点数精度误差, 做法就是下限减去误差, 上限加上误差
            return (x1 - ep <= x <= x2 + ep or x2 - ep <= x <= x1 + ep) and (y1 - ep <= y <= y2 + ep or y2 - ep <= y <= y1 + ep)

        # 先得到两条线段对应直线的斜率和截距
        k1, b1 = getKB(start1, end1)
        k2, b2 = getKB(start2, end2)
        # joints记录可能的有效交点
        joints = []
        if equal(k1, k2):
            # 两线段平行
            if equal(b1, b2):
                # 两线段位于同一直线上, 检查其是否重叠
                # 如果重叠的话, 需要求出交点中坐标最小的, 那么该点一定是重叠部分的端点, 因为中间部分的点的坐标一定介于两端点之间
                # 而重叠部分的端点显然属于两线段的端点, 所以问题转换成遍历2个线段的4个端点, 找同时在两线段内且坐标最小的
                joints = [start1, end1, start2, end2]
            else:
                # 两线段平行但是不在同一直线上, 一定无交点
                joints = []
        elif k1 == float("inf"):
            # 此时线段1是x=b1
            # 结合线段2, 交点自然是(b1, k2 * b1 + b2)
            joints = [(b1, k2 * b1 + b2)]
        elif k2 == float("inf"):
            # 此时线段2是x=b2
            # 结合线段1, 交点自然是(b2, k1 * b2 + b1)
            joints = [(b2, k1 * b2 + b1)]
        else:
            # 两直线不平行, 且都不平行于y轴
            # 联立两个y=kx+b方程求出两直线的交点
            joints = [((b2 - b1) / (k1 - k2), (b2 * k1 - b1 * k2) / (k1 - k2))]
        # 遍历可能的有效交点, 找最小坐标作为最终结果
        res = []
        for x, y in joints:
            if isInside(x, y, start1, end1) and isInside(x, y, start2, end2):
                # 当前端点同时在两线段内, 属于有效交点
                # 接下来检查其坐标是否最小, 是的话更新最终结果
                if not res or x < res[0] or x == res[0] and y < res[1]:
                    res = [x, y]
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我

程序员面试金典 - 面试题 16.03. 交点

题目描述

示例 1：

示例 2：

示例 3：

提示：

题目思考

解决方案

思路

复杂度

代码