数几何

直线和线段

字数统计: 2.5k字   |   阅读时长: 11分
, ,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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