数几何

多边形

字数统计: 3.2k字   |   阅读时长: 15分
, ,

摘要: 本文介绍计算几何中与多边形相关的基本问题

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

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

此后基于二维向量的代码模板，我们解决了计算几何中关于点、直线和线段、极角中的常见问题，以及力扣中的几个相关题目。

本文我们介绍计算几何中关于多边形的常见问题，代码依然使用 Vector2。然后解决三个力扣中的题目：469、593、836。主要涉及以下内容：

  • 凸多边形判定
  • 凸多边形点集排序
  • 简单多边形的面积
  • 简单多边形内部外部判断
  • 两个简单多边形相交

1. 凸多边形判定

  • 简单多边形：边不相交的多边形
  • 凸多边形：每个内角都在 180 度以内

题目：469. 凸多边形

给定 X-Y 平面上的一组点 points ，其中 points[i] = [xi, yi] 。这些点按顺序连成一个多边形。

如果该多边形为 凸 多边形（凸多边形的定义）则返回 true ，否则返回 false 。

你可以假设由给定点构成的多边形总是一个 简单的多边形（简单多边形的定义）。换句话说，我们要保证每个顶点处恰好是两条边的汇合点，并且这些边 互不相交 。

提示:

1
2
3
4
3 <= points.length <= 1e4
points[i].length == 2
-1e4 <= xi, yi <= 1e4
所有点都不同

示例 1：
输入: points = [[0,0],[0,5],[5,5],[5,0]]
输出: true

示例 2：
输入: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
输出: false

算法

枚举 i: 0,1,…,n，考察 p[i], p[(i+1)%n], p[(i+2)%n]，向量 Vector2 a(p[i], p[(i+1)%n]), Vector2 b(p[(i+1)%n], p[(i+2)%n])

b 相对于 a 的方向必须始终不变，两种情况：

  • b 始终在 a 的顺时针 180 度以内, 即 a, b 的叉积小于 0
  • b 始终在 a 的逆时针 180 度以内, 即 a, b 的叉积大于 0

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        int n = points.size();
        vector<int> p1 = points[0], p2 = points[1], p3 = points[2];
        Vector2 q1(p1[0], p1[1]);
        Vector2 q2(p2[0], p2[1]);
        Vector2 q3(p3[0], p3[1]);
        bool flag = ccw(q1, q2, q3) > EPS;
        for(int i = 0; i < n; ++i)
        {
            vector<int> p1 = points[i], p2 = points[(i + 1) % n], p3 = points[(i + 2) % n];
            Vector2 q1(p1[0], p1[1]);
            Vector2 q2(p2[0], p2[1]);
            Vector2 q3(p3[0], p3[1]);
            if(flag && ccw(q1, q2, q3) < -EPS)
                return false;
            if(!flag && ccw(q1, q2, q3) > EPS)
                return false;
        }
        return true;
    }
};

2. 凸多边形点集排序

选定点集的重心作为极点，然后对点集做极角排序。

1
2
计算点集的重心 O
计算点 Pi 之间的大小关系

大小关系定义：OPj 如果在 OPi 的逆时针方向，则 Pj 小于 Pi

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
struct Cmp
{
    Vector2 O;
    Cmp(Vector2 p0)
    {
        O = p0;
    }
    bool operator()(const Vector2& p1, const Vector2& p2) const
    {
        return ccw(O, p1, p2) > 0;
    }
};

题目：593. 有效的正方形

给定2D空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true 。

点的坐标 pi 表示为 [xi, yi] 。 输入没有任何顺序 。

一个 有效的正方形 有四条等边和四个等角(90度角)。

提示:

1
2
p1.length == p2.length == p3.length == p4.length == 2
-1e4 <= xi, yi <= 1e4

示例 1:
输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True

示例 2:
输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出：false

示例 3:
输入：p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
输出：true

算法

计算四个点重心，如果某个点与重心重合，直接返回false。

将点集排序。

然后枚举点 i，边1 (p[i], p[(i+1)%4]); 边2 (p[i], p[(i-1+4)%4])

  1. 模相同
  2. 夹角为 90 度(内积为零)

代码 (C++)

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
class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        vector<Vector2> points;
        points.emplace_back(p1[0], p1[1]);
        points.emplace_back(p2[0], p2[1]);
        points.emplace_back(p3[0], p3[1]);
        points.emplace_back(p4[0], p4[1]);
        Vector2 O(0, 0);
        for(Vector2 p: points)
        {
            O.x += p.x;
            O.y += p.y;
        }
        O.x /= 4;
        O.y /= 4;
        for(Vector2 p: points)
            if(fabs(p.x - O.x) < EPS && fabs(p.y - O.y) < EPS)
                return false;
        Cmp cmp(O);
        sort(points.begin(), points.end(), cmp);
        double c = (points[1] - points[0]).norm();
        for(int i = 0; i < 4; ++i)
        {
            cout << points[i].x << " " << points[i].y << endl;
            Vector2 a = points[(i + 1) % 4] - points[i];
            Vector2 b = points[(i - 1 + 4) % 4] - points[i];
            cout << a.x << " " << a.y << endl;
            cout << b.x << " " << b.y << endl;
            if(fabs(a.norm() - c) > EPS)
                return false;
            if(!a.perpendicular(b))
                return false;
        }
        return true;
    }
};

3. 简单多边形的面积

三角形

给出三角形三个顶点时，利用向量叉积就能求出面积。

凸多边形

选择多边形内部的一个点，用以该点为顶点的三角形分割多边形，求出各个三角形面积。

凹多边形

向量的叉积会根据不同方向而发生符号变化。利用此性质可以求凹多边形面积。

$\vec{a} \times \vec{b}$ 若要大于零，需要 $\vec{b}$ 在 $\vec{a}$ 的逆时针方向。

总结

假设简单多边形的 n 个顶点 $\vec{p}_{0}, \vec{p}_{1}, …, \vec{p}_{n-1}$ 已经按逆时针方向排列。

面积为

代码模板

1
2
3
4
5
6
7
8
9
// 简单多边形 p 的面积
double area(const vector<Vector2>& p)
{
    double ans = 0.0;
    int n = p.size();
    for(int i = 0; i < n; ++i)
        ans += p[i].cross(p[(i + 1) % n]);
    return fabs(ans) / 2.0;
}

题目：P1183 多边形的面积

本题是洛谷的题目，可以参考。有了 Vector2 和 ares 的代码模板，本题可以轻易解决，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
    int n;
    cin >> n;
    vector<Vector2> p;
    for(int i = 0; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        p.emplace_back(x, y);
    }
    int ans = area(p);
    cout << ans << endl;
}

4. 内部外部判断

给定多边形和不在多边形边上的点 q, 判断 q 在多边形内部还是外部。有面积和法和射线法。

面积和法(只适用与凸多边形)

判断 q 与多边形每条边组成的三角形面积的和是否等于多边形面积。

射线法

从 q 画一条射线，并计算与多边形的所有边的交点数目。

假象从 q 出发向右的射线，枚举每条边，判断该边能否将射线纵向分割，然后判断交点是否在 q 的右侧。

q 在多边形的边上时，射线法的结果不确定，需要单独处理。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 点 q 是否包含在多边形 p 内部
// q 在多边形边上没有处理
bool isInside(const vector<Vector2>& p, Vector2 q)
{
    int crosses = 0;
    int n = p.size();
    for(int i = 0; i < n; ++i)
    {
        int j = (i + 1) % n;
        // p[i], p[j] 能否纵向分割射线
        if((p[i].y > q.y) != (p[j].y > q.y))
        {
            // 交点的横坐标
            double X = (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x;
            if(q.x < X)
                ++crosses;
        }
    }
    return crosses % 2 == 1;
}

题目：凸多边形内点统计

本题是牛客的题目，可以参考。使用 Vector2 和射线法 isInside 的代码模板，本题比较好解决。

调用 isInside 前先判断点是否在多边形的边(线段)上，代码如下：

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
int main()
{
    int n;
    cin >> n;
    vector<Vector2> p;
    for(int i = 0; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        p.emplace_back(x, y);
    }
    int m;
    cin >> m;
    int ans = 0;
    for(int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;
        Vector2 q(x, y);
        bool flag = false;
        for(int i = 0; i < n; ++i)
        {
            int j = (i + 1) % n;
            if(fabs(ccw(p[i], p[j], q)) < EPS)
            {
                if((p[j] - p[i]).norm() > (p[j] - q).norm())
                {
                    flag = true;
                    continue;
                }
            }
        }
        if(flag)
            continue;
        if(isInside(p, q))
            ++ans;
    }
    cout << ans << endl;
}

$5 多边形相交

判定两个多边形是否互相接触(相连或重叠)。只有一个点重叠也是重叠。

  1. 枚举一个多边形的所有点，判定该点是否在另一个多边形内部，若是，则返回 true，若不是，则继续找相交或重叠线段。
  2. 找重叠或相交的边(线段)。

代码模板

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
// 仅判断两条线段是否相交，不需要交点
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;
}

// 判定对多边形 p 和 q 是否相交(相连或重叠)
// 只有一个点的重叠也是重叠
bool polygonIntersects(const vector<Vector2>& p, const vector<Vector2>& q)
{
    int n = p.size(), m = q.size();
    // 一个多边形的点在另一个多边形的内部
    if(isInside(p, q[0]) || isInside(q, p[0]))
        return true;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
        {
            if(segmentIntersection(p[i], p[(i + 1) % n], q[i], q[(i + 1) % n]))
                return true;
        }
    return false;
}

题目 836. 矩形重叠

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。

如果相交的面积为 正 ，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

提示：

1
2
3
4
rect1.length == 4
rect2.length == 4
-1e9 <= rec1[i], rec2[i] <= 1e9
rec1 和 rec2 表示一个面积不为零的有效矩形

示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false

示例 3：
输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3]
输出：false

代码 (C++)

需要特判矩形退化成线段的情况。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 仅判断两条线段是否相交，不需要交点
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(fabs(ab) < EPS || fabs(cd) < EPS)
        return false;
    return ab < 0 && cd < 0;
}

// 点 q 是否包含在多边形 p 内部
// q 在多边形边上没有处理
bool isInside(const vector<Vector2>& p, Vector2 q)
{
    int crosses = 0;
    int n = p.size();
    for(int i = 0; i < n; ++i)
    {
        int j = (i + 1) % n;
        // p[i], p[j] 能否纵向分割射线
        if((p[i].y > q.y) != (p[j].y > q.y))
        {
            // 交点的横坐标
            double X = (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x;
            if(q.x < X)
                ++crosses;
        }
    }
    return crosses % 2 == 1;
}

// 判定对多边形 p 和 q 是否相交(相连或重叠)
// 只有一个点的重叠也是重叠
bool polygonIntersects(const vector<Vector2>& p, const vector<Vector2>& q)
{
    int n = p.size(), m = q.size();
    // 一个多边形的点在另一个多边形的内部
    if(isInside(p, q[0]) || isInside(q, p[0]))
        return true;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
        {
            if(segmentIntersection(p[i], p[(i + 1) % n], q[j], q[(j + 1) % m]))
                return true;
        }
    return false;
}

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        vector<Vector2> p, q;
        p.emplace_back(rec1[0], rec1[1]);
        p.emplace_back(rec1[0], rec1[3]);
        p.emplace_back(rec1[2], rec1[3]);
        p.emplace_back(rec1[2], rec1[1]);
        q.emplace_back(rec2[0], rec2[1]);
        q.emplace_back(rec2[0], rec2[3]);
        q.emplace_back(rec2[2], rec2[3]);
        q.emplace_back(rec2[2], rec2[1]);
        int n = p.size(), m = q.size();
        // 矩形退化成直线的情况
        for(int i = 0; i < n; ++i)
        {
            if(fabs((p[(i + 1) % 4] - p[i]).norm()) < EPS)
                return false;
        }
        for(int j = 0; j < m; ++j)
        {
            if(fabs((q[(j + 1) % 4] - q[j]).norm()) < EPS)
                return false;
        }
        return polygonIntersects(p, q);
    }
};
Share