【计算几何】凸包问题 (Convex Hull)

【计算几何】凸包问题 (Convex Hull)

引言

凸多边形

凸多边形是指所有内角大小都在 [ 0 , π ] [0,π] [0,π]范围内的简单多边形

凸包

在平面上能包含所有给定点的最小凸多边形叫做凸包。

其定义为:对于给定集合 X,所有包含 X 的凸集的交集 S 被称为 X 的 凸包。

实际上可以理解为用一个橡皮筋包含住所有给定点的形态。

凸包用最小的周长围住了给定的所有点。如果一个凹多边形围住了所有的点,它的周长一定不是最小,如下图。根据三角不等式,凸多边形在周长上一定是最优的。

在这里插入图片描述

凸包的求法

主要介绍Graham扫描法

Graham Scan 算法求凸包

Graham Scan 算法是一种十分简单高效的二维凸包算法,能够在 O ( n l o g n ) O(nlogn) O(nlogn)
的时间内找到凸包。

Graham Scan 算法的做法是先确定一个起点(一般是最左边的点和最右边的点),然后一个个点扫过去,如果新加入的点和之前已经找到的点所构成的 “壳” 凸性没有变化,就继续扫,否则就把已经找到的最后一个点删去,再比较凸性,直到凸性不发生变化。分别扫描上下两个 “壳”,合并在一起,凸包就找到了。这么说很抽象,我们看图来解释:

在这里插入图片描述
在这里插入图片描述

先找 “下壳”,上下其实是一样的。首先加入两个点 A 和 B。

然后插入第三个点 C,并计算 A B ⃗ × B C ⃗ \vec{AB} \times \vec{BC} AB ×BC 的向量积,却发现向量积系数小于(等于)0,也就是说 B C ⃗ \vec{BC} BC
A B ⃗ \vec{AB} AB 的顺时针方向上。

在这里插入图片描述

于是删去 B 点。

在这里插入图片描述

按照这样的方法依次扫描,找完 “下壳” 后,再找 “上壳”。


#include <algorithm>

struct Point {
    double x, y;

    // 重载减法运算符,用于计算向量差
    Point operator-(Point& p) {
        Point t;
        t.x = x - p.x;
        t.y = y - p.y;
        return t;
    }

    // 计算向量叉积
    double cross(Point p) {
        return x * p.y - p.x * y;
    }
};

// 比较函数,用于排序点
bool cmp(Point& p1, Point& p2) {
    if (p1.x != p2.x) return p1.x < p2.x;
    return p1.y < p2.y;
}

Point point[1005];  // 无序点
int convex[1005];   // 保存组成凸包的点的下标
int n;              // 坐标系的无序点的个数

// 获取凸包的函数
int GetConvexHull() {
    // 按照x坐标排序,如果x相同则按照y坐标排序
    sort(point, point + n, cmp);
    int temp;
    int total = 0;

    // 构建下凸包
    for (int i = 0; i < n; i++) {
        // 如果当前栈中至少有两个点,并且新点使得栈顶的两个点与新点形成的向量不满足逆时针方向
        while (total > 1 &&
               (point[convex[total - 1]] - point[convex[total - 2]])
                       .cross(point[i] - point[convex[total - 1]]) <= 0)
            total--;  // 弹出栈顶点

        convex[total++] = i;  // 将当前点加入栈中
    }

    temp = total;  // 记录下凸包的点数

    // 构建上凸包
    for (int i = n - 2; i >= 0; i--) {
        // 如果当前栈中至少有两个点,并且新点使得栈顶的两个点与新点形成的向量不满足逆时针方向
        while (total > temp &&
               (point[convex[total - 1]] - point[convex[total - 2]])
                       .cross(point[i] - point[convex[total - 1]]) <= 0)
            total--;  // 弹出栈顶点

        convex[total++] = i;  // 将当前点加入栈中
    }

    return total - 1;  // 返回组成凸包的点的个数,实际上多了一个,就是起点,所以组成凸包的点个数是 total - 1
}

代码解释

结构体 Point:

  • 包含两个成员变量 x 和 y,表示点的坐标。

  • 重载了减法运算符 operator-,用于计算两个点的向量差。

  • 定义了 cross 方法,用于计算两个向量的叉积。

比较函数 cmp:

  • 用于对点进行排序,首先按 x 坐标排序,如果 x 坐标相同则按 y 坐标排序。

全局变量:

  • point 数组存储无序点。

  • convex 数组存储组成凸包的点的下标。

  • n 表示无序点的个数。

函数 G e t C o n v e x H u l l GetConvexHull GetConvexHull:

  • 首先对点进行排序。

  • 构建下凸包:从左到右遍历点,使用栈来维护凸包的点,确保每次新加入的点与栈顶的两个点形成的向量满足逆时针方向。

  • 构建上凸包:从右到左遍历点,使用栈来维护凸包的点,确保每次新加入的点与栈顶的两个点形成的向量满足逆时针方向。

  • 返回组成凸包的点的个数,注意实际点的个数是 total - 1,因为起点被重复计算了一次。

相关推荐

  1. 计算机视觉——OpenCV C++实现

    2024-07-09 22:14:04       7 阅读
  2. ——G - Highest Ratio

    2024-07-09 22:14:04       6 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-09 22:14:04       4 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-09 22:14:04       5 阅读
  3. 在Django里面运行非项目文件

    2024-07-09 22:14:04       4 阅读
  4. Python语言-面向对象

    2024-07-09 22:14:04       4 阅读

热门阅读

  1. RTOS系统 -- ARM Cortex-M4 RPMSG之通道初始化函数

    2024-07-09 22:14:04       8 阅读
  2. shell中不常见的命令

    2024-07-09 22:14:04       7 阅读
  3. 直播APP开发源码搭建

    2024-07-09 22:14:04       8 阅读
  4. 自己写个简单的vite插件

    2024-07-09 22:14:04       8 阅读
  5. ROS melodic版本卸载---Ubuntu18.04

    2024-07-09 22:14:04       9 阅读
  6. Ubuntu手动编译源码安装Python

    2024-07-09 22:14:04       8 阅读
  7. [C++][CMake][生成可执行文件][下]详细讲解

    2024-07-09 22:14:04       8 阅读
  8. ubuntu防火墙指定端口开放设置

    2024-07-09 22:14:04       10 阅读
  9. ubuntu20.04安装ros1

    2024-07-09 22:14:04       6 阅读
  10. 代码随想录算法训练营:26/60

    2024-07-09 22:14:04       7 阅读
  11. leetcode77组合——经典回溯算法

    2024-07-09 22:14:04       6 阅读
  12. 算法训练营day67

    2024-07-09 22:14:04       10 阅读