直线和线段

  |  

摘要: 本文介绍计算几何中与直线和线段相关的基本问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。

Vector2 类的对象既可以表示向量,又可以表示点,在文章 中,我们学习了计算几何中的一些关于点的问题。

本文我们介绍计算几何中关于直线和线段的常见问题,代码依然使用 Vector2,主要涉及以下内容:

  • 有向直线
    • 有向直线与点的位置关系
  • 直线与直线相交
    • 判断是否相交
    • 求交点
  • 线段与线段相交
    • 判断是否相交
    • 求交点

力扣中有两个相关的题目,面试题 16.03 和 面试题 16.13,题解代码也用的 Vector2 这个代码模板。


有向直线

点和方向向量的形式: $\vec{a} + p \cdot \vec{b}$。

Line 类的代码中使用 Vector2 表示点。

代码模板:直线类 Line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Line
{
// line: a+pb, a 是点, b 是方向向量
Vector2 a;
Vector2 b;
double deg; // 极角
Line(Vector2 a, Vector2 b):a(a),b(b)
{
deg = b.polar();
}
bool operator<(const Line& l) const
{
// 方向向量的极角序
return deg < l.deg;
}
};

点和有向直线的位置关系

判断一个点是否在有向直线的左侧。

代码模板

1
2
3
4
5
bool on_left(const Line& l, const Vector2& p)
{
// 点 p 是否在有向直线 l 左侧
return l.b.cross(p - l.a) > EPS;
}

直线与直线相交

两条直线的交点

解方程 $\vec{a} + p \cdot \vec{b} = \vec{c} + q \cdot \vec{d}$,求出 p 之后可以求出交点。

按横纵坐标的形式表示出来,联立

求解 p:

分母为零的情况:两个向量 $\vec{b}$ 和 $\vec{d}$ 平行。

代码模板

(1) 使用两个 Line 表示两个直线:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 直线与直线相交
bool line_intersection(const Line& l1, const Line& l2, Vector2& x)
{
double det = l1.b.cross(l2.b); // 两个方向向量的外积
// 平行或重叠返回false
if(fabs(det) < EPS)
return false;
// 两条有向直线的交点
Vector2 u = l1.a - l2.a;
double t = l2.b.cross(u) / det;
x = l1.a + l1.b * t;
return true;
}

(2) 使用 4 个 Vector2 表示两个直线

1
2
3
4
5
6
7
8
9
10
11
12
// 直线与直线相交
bool lineIntersection(Vector2 a, Vector2 b, Vector2 c, Vector2 d, Vector2& x)
{
// 平行或重叠返回 false
// (b - a) 是 (a, b) 的方向向量
// (d - c) 是 (c, d) 的方向向量
double det = (b - a).cross(d - c);
if(fabs(det) < EPS)
return false;
x = a + (b - a) * ((c - a).cross(d - c) / det);
return true;
}

线段与线段相交

首先算出两条直线的交点,然后判断直线的交点是否在线段上。但是有额外的 Corner Case:

同一条直线上出现两条线段的情况:

  • 两条线段互相不重叠
  • 两条线段相接于一点
  • 两条线段互相重叠
  • 一条线段包含另一条

(1) 判断并返回交点

代码模板

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
// 两条直线平行时,判断两条线段是否属于同一直线且有重叠或相接于一点
bool parallelSegments(Vector2 a, Vector2 b, Vector2 c, Vector2 d, Vector2& x)
{
// (a, b) , (c, d) 平行时,判断是否相接于一点
if(b < a) swap(a, b);
if(d < c) swap(c, d);
// 两条线段不在同一条直线以及两条线段不重叠的情况
if(ccw(a, b, c) != 0 || b < c || d < a) return false;
if(a < c)
x = c;
else
x = a;
return true;
}

// 判断交点是否落在线段上
bool inBoundingRectangle(Vector2 x, Vector2 a, Vector2 b)
{
// x, a, b 同线
// 判断 x 是否在包含 (a, b) 且各边平行于 x 轴,y 轴的最小四边形内部。
if(b < a) swap(a, b);
return x == a || x == b || (a < x && x < b);
}

// 线段与线段相交
bool segmentIntersection(Vector2 a, Vector2 b, Vector2 c, Vector2 d, Vector2& x)
{
// 将 (a, b) , (c, d) 的交点返回 x
// 多个交点返回 x 最小的,x 相同的情况下返回 y 最小的
// 不相交返回 false
if(!lineIntersection(a, b, c, d, x))
{
// 两条线段平行
return parallelSegments(a, b, c, d, x);
}
// 两条直线有交点 x
// 仅当两条线段都包含 x 时返回真
return inBoundingRectangle(x, a, b) && inBoundingRectangle(x, c, d);
}

(2) 仅判断,不用返回交点

简单用向量的 ccw() 函数即可。

如果 (a, b)(c, d) 相交,则 ccw(a, b, c)ccw(a, b, d) 异号,以及 ccw(c, d, a)ccw(c, d, b) 异号。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
bool segmentIntersection(Vector2 a, Vector2 b, Vector2 c, Vector2 d)
{
double ab = ccw(a, b, c) * ccw(a, b, d);
double cd = ccw(c, d, a) * ccw(c, d, b);
// 两条线段在同一直线上或者端点相互重叠
if(ab == 0 && cd == 0)
{
if(b < a) swap(a, b);
if(d < c) swap(c, d);
return !(b < c || d < a);
}
return ab <= 0 && cd <= 0;
}

题目 面试题 16.03. 交点

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

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

提示:

1
2
坐标绝对值不会超过 2^7
输入的坐标均是有效的二维坐标

示例 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}
输出: {},两条线段没有交点

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
Vector2 a(start1[0], start1[1]);
Vector2 b(end1[0], end1[1]);
Vector2 c(start2[0], start2[1]);
Vector2 d(end2[0], end2[1]);
Vector2 x(0, 0);
bool flag = segmentIntersection(a, b, c, d, x);
if(!flag)
return {};
return {x.x, x.y};
}
};

题目 面试题 16.13. 平分正方形

给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平行。

每个正方形的数据square包含3个数值,正方形的左下顶点坐标[X,Y] = [square[0],square[1]],以及正方形的边长square[2]。所求直线穿过两个正方形会形成4个交点,请返回4个交点形成线段的两端点坐标(两个端点即为4个交点中距离最远的2个点,这2个点所连成的线段一定会穿过另外2个交点)。2个端点坐标[X1,Y1]和[X2,Y2]的返回格式为{X1,Y1,X2,Y2},要求若X1 != X2,需保证X1 < X2,否则需保证Y1 <= Y2。

若同时有多条直线满足要求,则选择斜率最大的一条计算并返回(与Y轴平行的直线视为斜率无穷大)。

提示:

1
2
square.length == 3
square[2] > 0

示例:
输入:
square1 = {-1, -1, 2}
square2 = {0, -1, 2}
输出: {-1,0,2,0}
解释: 直线 y = 0 能将两个正方形同时分为等面积的两部分,返回的两线段端点为[-1,0]和[2,0]

代码 (C++)

首先根据 (x, y, len) 求出右上角点和中心点,如果两个中心点重合,返回经过中心点的与 x 轴垂直的直线与正方形的两个交点。

两个中心点不重合,两个中心点 O1 和 O2 形成一条直线。

分别求直线与八条线段所在直线的交点,然后判断该点是否在线段上,如果在,加入到候选 cand 中。

最后将 cand 中的点按照横纵坐标进行双关键字排序,返回排序后的头和尾两个点。

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
54
55
56
57
58
59
60
61
// 直线与直线相交
bool lineIntersection(Vector2 a, Vector2 b, Vector2 c, Vector2 d, Vector2& x)
{
// 平行或重叠返回 false
// (b - a) 是 (a, b) 的方向向量
// (d - c) 是 (c, d) 的方向向量
double det = (b - a).cross(d - c);
if(fabs(det) < EPS)
return false;
x = a + (b - a) * ((c - a).cross(d - c) / det);
return true;
}

// 判断交点是否落在线段上
bool inBoundingRectangle(Vector2 x, Vector2 a, Vector2 b)
{
// x, a, b 同线
// 判断 x 是否在包含 (a, b) 且各边平行于 x 轴,y 轴的最小四边形内部。
if(b < a) swap(a, b);
return x == a || x == b || (a < x && x < b);
}

class Solution {
public:
vector<double> cutSquares(vector<int>& square1, vector<int>& square2) {
Vector2 A1(square1[0], square1[1]), A2(square1[0] + square1[2], square1[1] + square1[2]);
Vector2 B1(square2[0], square2[1]), B2(square2[0] + square2[2], square2[1] + square2[2]);
Vector2 O1 = (A1 + A2) * 0.5;
Vector2 O2 = (B1 + B2) * 0.5;
if(O1 == O2)
{
return {O1.x, min(A1.y, B1.y), O1.x, max(A2.y, B2.y)};
}
Vector2 A3(square1[0], square1[1] + square1[2]), A4(square1[0] + square1[2], square1[1]);
Vector2 B3(square2[0], square2[1] + square2[2]), B4(square2[0] + square2[2], square2[1]);
vector<Vector2> A{A1, A3, A2, A4};
vector<Vector2> B{B1, B3, B2, B4};
vector<Vector2> cand;
traverse_edge(A, cand, O1, O2);
traverse_edge(B, cand, O1, O2);
sort(cand.begin(), cand.end());
return {cand.front().x, cand.front().y, cand.back().x, cand.back().y};
}

private:
void traverse_edge(const vector<Vector2>& A, vector<Vector2>& cand, const Vector2& O1, const Vector2& O2)
{
for(int i = 0; i < 4; ++i)
{
Vector2 p1 = A[i], p2 = A[(i + 1) % 4];
Vector2 X;
if(lineIntersection(p1, p2, O1, O2, X))
{
if(inBoundingRectangle(X, p1, p2))
{
cand.push_back(X);
}
}
}
}
};

Share