class Solution {
public:
vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
}
};
面试题 16.03. 交点
给定两条线段（表示为起点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}
输出： {}，两条线段没有交点
提示：
原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 40.4 MB, 提交时间: 2023-04-22 11:16:54
class Solution {
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[] ans = new double[2];
Arrays.fill(ans, Double.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 (isInside(x1, y1, x2, y2, x3, y3)) {
updateRes(ans, x3, y3);
}
// 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上
if (isInside(x1, y1, x2, y2, x4, y4)) {
updateRes(ans, (double)x4, (double)y4);
}
// 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上
if (isInside(x3, y3, x4, y4, x1, y1)) {
updateRes(ans, (double)x1, (double)y1);
}
// 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上
if (isInside(x3, y3, x4, y4, x2, y2)) {
updateRes(ans, (double)x2, (double)y2);
}
}
} else {
// 联立方程得到 t1 和 t2 的值
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));
// 判断 t1 和 t2 是否均在 [0, 1] 之间
if (t1 >= 0.0 && t1 <= 1.0 && t2 >= 0.0 && t2 <= 1.0) {
ans[0] = x1 + t1 * (x2 - x1);
ans[1] = y1 + t1 * (y2 - y1);
}
}
if (ans[0] == Double.MAX_VALUE) {
return new double[0];
}
return ans;
}
// 判断 (x, y) 是否在「线段」(x1, y1)~(x2, y2) 上
// 这里的前提是 (x, y) 一定在「直线」(x1, y1)~(x2, y2) 上
private boolean isInside(int x1, int y1, int x2, int y2, int x, int y) {
// 若与 x 轴平行，只需要判断 x 的部分
// 若与 y 轴平行，只需要判断 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 updateRes(double[] ans, double x, double y) {
if (x < ans[0] || (x == ans[0] && y < ans[1])) {
ans[0] = x;
ans[1] = y;
}
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2023-04-22 11:15:20
class Solution:
def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2
det = lambda a, b, c, d: a * d - b * c
d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)
p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)
q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)
if d != 0:
lam, eta = p / d, q / d
if not (0 <= lam <= 1 and 0 <= eta <= 1): return []
return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]
if p != 0 or q != 0: return []
t1, t2 = sorted([start1, end1]), sorted([start2, end2])
if t1[1] < t2[0] or t2[1] < t1[0]: return []
return max(t1[0], t2[0])
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2023-04-22 11:14:18
class Solution:
def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
# 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上
# 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上
def inside(x1, y1, x2, y2, xk, yk):
# 若与 x 轴平行，只需要判断 x 的部分
# 若与 y 轴平行，只需要判断 y 的部分
# 若为普通线段，则都要判断
return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))
def update(ans, xk, yk):
# 将一个交点与当前 ans 中的结果进行比较
# 若更优则替换
return [xk, yk] if not ans or [xk, yk] < ans else ans
x1, y1 = start1
x2, y2 = end1
x3, y3 = start2
x4, y4 = end2
ans = list()
# 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行
if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):
# 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上
if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):
# 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上
if inside(x1, y1, x2, y2, x3, y3):
ans = update(ans, x3, y3)
# 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上
if inside(x1, y1, x2, y2, x4, y4):
ans = update(ans, x4, y4)
# 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上
if inside(x3, y3, x4, y4, x1, y1):
ans = update(ans, x1, y1)
# 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上
if inside(x3, y3, x4, y4, x2, y2):
ans = update(ans, x2, y2)
# 在平行时，其余的所有情况都不会有交点
else:
# 联立方程得到 t1 和 t2 的值
t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))
t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))
# 判断 t1 和 t2 是否均在 [0, 1] 之间
if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:
ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]
return ans