难度: Hard
给定两条线段（表示为起点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}
输出： {}，两条线段没有交点
提示：
运行时间: 20 ms
内存: 16.7 MB
class Solution:
def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
x1, y1 = start1
x2, y2 = end1
x3, y3 = start2
x4, y4 = end2
def inline(x1, y1, x2, y2, xk, yk):
return (min(x1, x2) <= xk <= max(x1, x2)) and (min(y1, y2) <= yk <= max(y1, y2))
ans = []
if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):
# 平行
if (y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1):
# 共线
if inline(x3, y3, x4, y4, x1, y1):
if not ans or ans > [x1, y1]:
ans = [x1, y1]
if inline(x3, y3, x4, y4, x2, y2):
if not ans or ans > [x2, y2]:
ans = [x2, y2]
if inline(x1, y1, x2, y2, x3, y3):
if not ans or ans > [x3, y3]:
ans = [x3, y3]
if inline(x1, y1, x2, y2, x4, y4):
if not ans or ans > [x4, y4]:
ans = [x4, y4]
else:
# 不平行
t1 = ((x1 - x3) * (y4 - y3) - (y1 - y3) * (x4 - x3)) / ((y2 - y1) * (x4 - x3) - (x2 - x1) * (y4 - y3))
t2 = ((x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1)) / ((y4 - y3) * (x2 - x1) - (y2 - y1) * (x4 - x3))
if 0 <= t1 <= 1 and 0 <= t2 <= 1:
ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]
return ans
此题解首先通过直线方程和线段端点位置关系判断两线段是否平行或共线。如果平行且共线，再判断线段是否有重叠部分，并选出最小的交点。如果不平行，使用线性方程组来找到潜在的交点，并检查该点是否同时在两条线段上。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
# Extract coordinates from the input
x1, y1 = start1
x2, y2 = end1
x3, y3 = start2
x4, y4 = end2
# Helper function to check if a point is within a segment
def inline(x1, y1, x2, y2, xk, yk):
return (min(x1, x2) <= xk <= max(x1, x2)) and (min(y1, y2) <= yk <= max(y1, y2))
ans = []
# Check parallelism
if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):
# Check colinearity
if (y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1):
# Check if the segments overlap and find the smallest intersection point
if inline(x3, y3, x4, y4, x1, y1):
if not ans or ans > [x1, y1]:
ans = [x1, y1]
if inline(x3, y3, x4, y4, x2, y2):
if not ans or ans > [x2, y2]:
ans = [x2, y2]
if inline(x1, y1, x2, y2, x3, y3):
if not ans or ans > [x3, y3]:
ans = [x3, y3]
if inline(x1, y1, x2, y2, x4, y4):
if not ans or ans > [x4, y4]:
ans = [x4, y4]
else:
# Calculate potential intersection point using line equations
t1 = ((x1 - x3) * (y4 - y3) - (y1 - y3) * (x4 - x3)) / ((y2 - y1) * (x4 - x3) - (x2 - x1) * (y4 - y3))
t2 = ((x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1)) / ((y4 - y3) * (x2 - x1) - (y2 - y1) * (x4 - x3))
if 0 <= t1 <= 1 and 0 <= t2 <= 1:
ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]
return ans
在二维空间中，两条线段是否平行可以通过检查它们的斜率是否相等来判断。这可以通过交叉乘积来实现，因为交叉乘积在数值上等于两向量的斜率之差。在代码中，判断两线段平行的条件是 `(y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3)`。这个条件实际上检查了线段(start1, end1)和线段(start2, end2)的斜率是否相等。如果两线段之间的斜率相同，交叉乘积为零，这意味着没有垂直分量，因此两线段平行。
当确定线段共线时，代码通过对线段端点进行比较来找出X值最小的交点，如果X值相同则比较Y值。首先，代码检查每个线段的端点是否在另一个线段上，使用辅助函数`inline`。然后，通过比较当前找到的交点`ans`与新考虑的端点，更新`ans`为较小的一个。具体实现为：在每次找到一个端点在另一线段上时，通过条件`if not ans or ans > [xk, yk]`来更新`ans`。这里`ans > [xk, yk]`利用了Python列表的比较规则：首先比较列表的第一个元素，如果相同则比较下一个元素。因此，这种方法首先确保X值是最小的，如果X值相同，则确保Y值是最小的。
当两线段不平行时，可以通过解线性方程组来找到它们的交点。首先，对于每条线段可以表示为参数方程：线段(start1, end1)表示为 `x1 + t1 * (x2 - x1)` 和 `y1 + t1 * (y2 - y1)`，线段(start2, end2)表示为 `x3 + t2 * (x4 - x3)` 和 `y3 + t2 * (y4 - y3)`。将这两个方程组合并整理得到两个方程关于`t1`和`t2`的表达式。然后解这个方程组来找到`t1`和`t2`的值。如果`0 <= t1 <= 1`和`0 <= t2 <= 1`，则交点在两条线段上。代码中的`t1`和`t2`的计算表达式分别是：`t1 = ((x1 - x3) * (y4 - y3) - (y1 - y3) * (x4 - x3)) / ((y2 - y1) * (x4 - x3) - (x2 - x1) * (y4 - y3))` 和 `t2 = ((x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1)) / ((y4 - y3) * (x2 - x1) - (y2 - y1) * (x4 - x3))`。如果这些值在0到1的范围内，这意味着交点确实位于两条线段的实际长度内。