交点
难度:
标签:
题目描述
Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any. If there's no intersection, return an empty array.
The absolute error should not exceed 10^-6. If there are more than one intersections, return the one with smallest X axis value. If there are more than one intersections that have same X axis value, return the one with smallest Y axis value.Example 1:
Input:
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
Output: {0.5, 0}
Example 2:
Input:
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
Output: {1, 1}
Example 3:
Input:
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
Output: {} (no intersection)
Note:
- The absolute value of coordinate value will not exceed 2^7.
- All coordinates are valid 2D coordinates.
代码结果
运行时间: 20 ms, 内存: 16.7 MB
/*
* 思路：
* 1. 使用Stream计算交点，遵循与Java解法相同的逻辑。
*/
import java.util.Optional;
import java.util.stream.Stream;
public class SolutionStream {
public Optional<double[]> intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
double x1 = start1[0], y1 = start1[1];
double x2 = end1[0], y2 = end1[1];
double x3 = start2[0], y3 = start2[1];
double x4 = end2[0], y4 = end2[1];
double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
if (denom == 0) { // 平行或共线
return Optional.empty();
}
double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;
return Stream.of(new double[] {x1 + ua * (x2 - x1), y1 + ua * (y2 - y1)})
.filter(point -> ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1)
.findFirst();
}
}解释
方法:
此题解首先通过直线方程和线段端点位置关系判断两线段是否平行或共线。如果平行且共线，再判断线段是否有重叠部分，并选出最小的交点。如果不平行，使用线性方程组来找到潜在的交点，并检查该点是否同时在两条线段上。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
如何准确判断两条线段是否平行？在代码中是根据什么条件来判断两线段平行的？
▷🦆
在处理共线情况时，如何确保找到的交点是X值最小的，如果X值相同，如何保证Y值最小？
▷🦆
代码中提到使用线性方程组来计算交点，能否详细解释这一计算过程？
▷