计算几何中与多边形相关的基本问题

潮汐朝夕

上海交通大学信息与通信工程硕士

摘要: 本文介绍计算几何中与多边形相关的基本问题
【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站： 潮汐朝夕的生活实验室
我的公众号： 算法题刷刷
我的知乎： 潮汐朝夕
我的github： FennelDumplings
我的leetcode： FennelDumplings

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

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

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

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

1. 凸多边形判定

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

题目： 469. 凸多边形

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

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

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

提示:

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++)

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. 凸多边形点集排序

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

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

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

代码模板

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度角)。

提示:

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])

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

代码 (C++)

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} 已经按逆时针方向排列。

面积为

\frac{1}{2}(\vec{p}_{0} \times \vec{p}_{1} + \vec{p}_{1} \times \vec{p}_{2} + ... + \vec{p}_{n-2} \times \vec{p}_{n-1} + \vec{p}_{n-1} \times \vec{p}_{0}) \\

代码模板

// 简单多边形 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 的代码模板，本题可以轻易解决，代码如下：

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 在多边形的边上时，射线法的结果不确定，需要单独处理。

代码模板

// 点 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 前先判断点是否在多边形的边(线段)上，代码如下：

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 多边形相交

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

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

代码模板

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

提示：

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++)

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

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

1. 凸多边形判定

题目： 469. 凸多边形

算法

代码 (C++)

2. 凸多边形点集排序

代码模板

题目： 593. 有效的正方形

算法

代码 (C++)

3. 简单多边形的面积

三角形

凸多边形

凹多边形

总结

代码模板

题目： P1183 多边形的面积

4. 内部外部判断

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

射线法

代码模板

题目： 凸多边形内点统计

$5 多边形相交

代码模板

题目 836. 矩形重叠

代码 (C++)

题目：凸多边形内点统计