0%

leetcode 面试题16.03 交点

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 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}
输出: {},两条线段没有交点

思路:使用点斜式解方程,斜率不存在时单独考虑。

斜率不存在时

  • (1)都不存在
    判断是否重叠,是则返回答案,否则返回空
  • (2)$line1$不存在$line2$存在
    求出交点判断交点是否在线段范围内
  • (3)$line1$存在$line2$不存在
    同(2)

由$y=kx+b$,斜率存在时有$k=(y_1-y_2)/(x_1-x_2)$,$b=y_1-k*x_1$
所以每两个点确定一个方程,当两条线段斜率都存在时:
两直线方程为:

$y=k_1*x+b_1$

$y=k_2*x+b_2$

若两线的平行

  • (1)不重叠,则无交点
  • (2)重叠,返回重叠的线段中x坐标的最小的点,x相同时返回y坐标最小的点。

否则联立方程得一交点,解之得$x=(b_2-b_1)/(k_1-k_2)$,$y=k1*x+b1$
判断此交点是否在线段范围内即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
if(start1[0] > end1[0])swap(start1,end1);//将点按照x的大小放
if(start2[0] > end2[0])swap(start2,end2);
bool flag1=0,flag2=0;
if(start1[0] - end1[0] == 0)flag1=1;
if(start2[0] - end2[0] == 0)flag2=1;
if(flag1 && flag2){ //都垂直x
if(start1[0] != start2[0])return {};
else{
//返回最小y的点
int x1[2]={min(start1[1],end1[1]),max(start1[1],end1[1])};
int x2[2]={min(start2[1],end2[1]),max(start2[1],end2[1])};
int ly = max(x1[0],x2[0]),ry=min(x1[1],x2[1]);
if(ly>ry)return {};
return {(double)start1[0],(double)ly};
}
}else if(flag1 && !flag2){//第一条垂直x第二条不垂直x
return check(start1,end1,start2,end2);
}else if(!flag1 && flag2){//第一条不垂直x第二条垂直x
return check(start2,end2,start1,end1);
}else{ //都不垂直x
double k1 = (double)(end1[1] - start1[1]) / (end1[0] - start1[0]);
double b1 = start1[1] - k1 * start1[0];
double k2 = (double)(end2[1] - start2[1])/(end2[0] - start2[0]);
double b2 = start2[1] - k2 * start2[0];
if(k1 == k2){ //平行
if(b1==b2){ //重叠 返回x最小 x相同返回y最小
int lx = max(start1[0],start2[0]),rx=min(end1[0],end2[0]);
if(lx>rx)return {};
if(lx>start1[0])return {(double)start2[0],(double)start2[1]};
else return {(double)start1[0],(double)start1[1]};
}else return {};
}else{
double interx = (b2-b1)/(k1-k2),intery=k1*interx + b1;
int x1=min(start1[0],end1[0]),x2=max(start1[0],end1[0]);
int x3=min(start2[0],end2[0]),x4=max(start2[0],end2[0]);
if(interx>=x1 && interx<=x2 && interx>=x3 && interx<=x4){
return {interx,intery};
}
else return {};
}
}
}
vector<double> check(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2){
double k2 = (double)(end2[1] - start2[1])/(end2[0] - start2[0]);
double b2 = start2[1] - k2 * start2[0];
double interx = start1[0],intery = k2*interx + b2;
if(intery>=min(start1[1],end1[1]) && intery <= max(start1[1],end1[1]))return {interx,intery};
else return {};
}
};