C++ 凸包算法

2025年3月22日 | 阅读 17 分钟

揭秘凸包算法的优雅：全面探索

凸包算法 是计算几何领域的重要基石，为解决一个基本问题提供了高效的解决方案：找到一个最小的凸多边形，该多边形包含平面上给定的一组点。这个问题，即凸包问题，在图像处理、计算机图形学、机器人技术和地理信息系统等领域有着广泛的应用。对这个几何挑战的最佳解决方案的追求促使了各种算法的发展，每种算法都有其独特的特性和效率。在这篇全面的探索中，我们将揭示凸包算法的理论基础，深入探讨其设计的复杂性，并阐明其应用。

理解凸包问题

平面上一组点的凸包是包含所有给定点的最小凸多边形。凸多边形是指连接多边形内任意两点的线段完全位于多边形内部。凸包问题可以正式定义为找到构成这个最小凸多边形边界的顶点的集合。

凸包问题的重要性延伸到许多领域。例如，在计算机图形学中，凸包对于渲染逼真且视觉上吸引人的场景至关重要。在机器人技术中，理解凸包有助于碰撞检测和路径规划。地理信息系统利用凸包算法来有效地描绘地理区域的边界。应用范围广泛，使得对最佳凸包算法的探索既在理论上引人入胜，又在实践中至关重要。

凸包算法的类型

凸包算法可以广义地分为增量法、分治法和包礼物算法。每种类别都带来了自己的一系列技术和权衡，丰富了凸包算法的图景。

1. 增量法

增量法逐步构建凸包，一次将一个点添加到现有的凸包中。一种流行的增量算法是Graham 扫描法。它从选择具有最低y 坐标的点（如果相同则选择最左边的点）作为枢轴开始。然后根据点相对于枢轴的极角对剩余点进行排序。逐个处理排序后的点以构建凸包。虽然高效，但增量法可能对点插入的顺序敏感。

2. 分治法

分治算法将问题分解为更小的子问题，递归地求解它们，然后组合结果以获得凸包。QuickHull算法就是一种分治方法的例子。它选择两个极值点，根据点相对于连接极值点的线的相对位置将点分成两组，并对每个子集递归地应用该算法。然后合并结果以获得凸包。

3. 包礼物算法

包礼物算法也称为 Jarvis March 或包礼物算法。它以一个已知在凸包上的点开始，并根据相对于当前点的极角迭代地选择极角最小的点。此过程一直持续到凸包完成为止。包礼物算法直观且易于实现，Jarvis March 是一个经典示例。

Graham 扫描法：优雅地导航凸包

Graham 扫描法，作为增量凸包算法的标志性代表，以一系列精心编排的步骤优雅地构建凸包。该算法的优雅之处在于其简单性和效率。

Graham 扫描法的关键步骤

枢轴选择

识别具有最低 y 坐标的点（如果相同则选择最左边的点）作为枢轴。

按极角排序

根据点相对于枢轴的极角对剩余点进行排序。这涉及为每个点计算极角并将其用作排序标准。

构建凸包

逐个遍历排序后的点，将每个点添加到凸包中。

对于每个点，检查当前点、凸包上的顶部点和排序顺序中的下一个点形成的角度是否为左转。如果是，则将该点添加到凸包中；否则，从凸包中移除顶部点，直到遇到左转。

完成凸包

此时凸包已完成，由在迭代过程中添加的点组成。

Graham 扫描法优雅地处理凸包问题的复杂性，以O(n log n)的时间复杂度高效地构建凸包，其中 n 是输入点的数量。其增量性质和对极角的依赖有助于其直观的设计和有效性。

Graham 扫描法以数学家Ronald Graham的名字命名，通过一系列增量步骤优雅地构建凸包。它因其简单性、效率和直观的几何基础而备受推崇。该算法的总体策略包括选择一个枢轴点，根据剩余点相对于枢轴的极角进行排序，并按顺序考虑排序点来迭代地构建凸包。

1. 枢轴选择

算法首先选择一个枢轴点，通常选择 y 坐标最低的点。如果多个点共享相同的 y 坐标，则选择其中最左边的点作为枢轴。此枢轴点保证是凸包的一部分。

2. 按极角排序

选择枢轴后，根据剩余点相对于枢轴的极角进行排序。极角使用三角函数计算，建立一个以枢轴为原点的坐标系。

按极角排序可确保在遍历排序列表时，相对于枢轴按逆时针顺序遇到点。此顺序对于凸包构建过程至关重要。

3. 构建凸包

有了排序后的点，Graham 扫描法会遍历它们，依次考虑每个点来增量地构建凸包。

算法使用堆栈来维护凸包上的点。最初，枢轴和前两个排序后的点被压入堆栈。

对于每个后续点，算法会检查将该点添加到凸包是否会产生左转。如果检测到左转，则将该点添加到凸包中；否则，从堆栈中弹出点，直到实现左转。

此过程一直持续到考虑完所有点，凸包由堆栈上的点组成。

4. 完成凸包

凸包，由堆栈上的点表示，现已完成。添加点的顺序确保以逆时针方式形成凸包。

Graham 扫描法实现了简单性和效率之间的平衡。排序步骤将其时间复杂度贡献为 O(n log n)，其中 n 是输入点的数量。该算法的增量性质使其能够很好地适应动态数据集，其中点会随时间添加或删除。

几何洞察力和效率

Graham 扫描法的成功在于其对几何特性的利用。通过考虑极角，该算法确保按逆时针顺序处理点，这与凸多边形的基本原理一致。左转测试，算法的一个关键方面，决定了将一个点添加到凸包是否会产生左转。此测试是建立凸包的凸性并有助于多边形的正确构建的基础。

凸包简介

为了充分理解 Graham 扫描法，有必要理解凸包的概念。凸包是包含给定点集的最小凸多边形。凸性意味着连接多边形内任意两点的线段完全位于多边形内部。凸包问题出现在各种应用中，从计算机图形学和计算几何到机器人技术和地理信息系统。

对动态数据的适应性

Graham 扫描法非常适合动态场景，其中点会增量地添加或删除。其增量性质使其能够无缝地适应数据集的变化，而无需完全重新计算凸包。在数据集随时间演变的应用中，这种适应性是一项宝贵的特性。

局限性和注意事项

虽然 Graham 扫描法是一种强大的算法，但它并非没有局限性。该算法假设输入数据集中的任意三个点都不共线。共线点可能会干扰左转测试，从而可能导致不正确的结果。因此，可能需要预处理步骤来处理共线点或选择合适的枢轴。

实际应用

凸包算法的实际应用，包括 Graham 扫描法等增量方法，具有广泛的应用，涵盖各个领域，利用这些算法提供的效率和几何洞察力。在这里，我们深入探讨计算机科学、机器人技术、地理和图像处理等领域的具体实际应用。

1. 计算机图形学：优化渲染和可见性确定

在计算机图形学领域，凸包算法在优化渲染过程和确定场景中对象的可见性方面发挥着至关重要的作用。对象的凸包有助于识别场景的外边界，使图形引擎能够将渲染工作集中在可见部分。这种优化在实时图形（如视频游戏或虚拟模拟）中尤为重要，因为此时计算资源有限，渲染效率至关重要。

可见性确定

凸包算法有助于确定场景的哪些部分从给定视点可见。通过计算场景中对象的凸包，图形引擎可以快速识别可见表面并简化渲染管线。这有助于更流畅、更高效的渲染，尤其是在复杂的 3D 环境中。

碰撞检测

除了可见性确定之外，凸包算法还用于计算机图形学中的碰撞检测。通过将对象表示为凸形状，碰撞检测算法可以有效地检查对象之间的交集和重叠。这在准确的碰撞检测至关重要的应用程序中至关重要，例如模拟、虚拟现实环境和交互式游戏体验。

2. 机器人技术：路径规划和避碰

凸包算法在机器人技术领域得到了广泛的应用，为路径规划和避碰挑战提供了解决方案。在机器人系统中，理解障碍物的凸包并有效地绕过它们是安全和最优机器人运动的基础。

路径规划

凸包算法有助于定义机器人可以在环境中导航的可用自由空间。通过计算障碍物的凸包，规划器可以识别机器人要穿越的清晰路径。这对于需要导航动态变化环境并避免碰撞的自主机器人、无人机和其他机器人系统至关重要。

避碰

实时避碰是机器人技术中的一个关键方面，尤其是在机器人与人类或其他机器人共享空间的情况下。凸包提供了障碍物的简化表示，能够快速进行碰撞检查并做出有效的决策以避免潜在的碰撞。

3. 地理信息系统 (GIS)：边界定义和空间分析

地理信息系统 (GIS) 依赖凸包算法来执行边界定义、空间分析和地图绘制等任务。凸包有助于描绘地理区域的边界，并有助于空间数据的有效表示。

边界定义

在 GIS 应用中，凸包算法有助于定义地理区域的边界。这在土地测量等任务中尤其有用，其中凸包可以表示测量区域的最外层限制或定义行政边界。

空间分析

凸包用于空间分析，以简化和分析复杂的空间数据集。例如，在生态研究中，凸包可用于根据观察点描绘特定物种的领地或范围，有助于栖息地分析和野生动物管理。

4. 图像处理：对象识别和形状分析

凸包算法在图像处理中找到应用，有助于对象识别、形状分析和从图像中提取有意义的特征。

对象识别

在图像处理中，凸包被用作对象识别的工具。通过将对象表示为凸形状，算法可以识别独特的特征和模式。这在计算机视觉等应用程序中很有价值，在这些应用程序中，识别和分类图像中的对象是一项常见任务。

形状分析

凸包在形状分析中发挥作用，有助于量化和描述图像中对象的整体结构。这在医学成像中用于分析解剖形状或在工业环境中用于检查制造组件的形状时很有益。

凸包算法的实际应用，以 Graham 扫描法等增量方法为例，涵盖了广泛的领域，有助于提高效率、优化和决策。从优化计算机图形学的渲染到增强机器人技术的导航，在 GIS 中定义边界，以及在图像处理中协助对象识别，凸包算法都作为多功能的工具。随着技术的不断进步，凸包算法在解决复杂的几何问题和为各个学科做出贡献的作用有望进一步扩大。

Graham 扫描法作为增量凸包算法的代表，体现了几何洞察力和算法效率的结合。其逐步构建方法，利用极角和左转测试，能够以逆时针顺序形成凸包。该算法已在从计算机图形学到机器人技术和 GIS 的各种领域找到了应用。当我们深入研究 Graham 扫描法的复杂性时，我们不仅发现了它的理论基础，还发现了它在应对复杂的几何挑战方面的实际影响和多功能性。

QuickHull：分治法的奇迹

在分治凸包算法领域，QuickHull 成为效率的奇迹。其分治策略，加上仔细的几何分析，使其能够以简单性和速度之间令人信服的平衡来构建凸包。

QuickHull 的关键步骤

初始选择

识别 x 坐标最小和最大的两个点；这两个点将作为凸包的端点。

划分点

根据点相对于连接两个端点的线的相对位置，将剩余点划分为两组。

递归

递归地将 QuickHull 算法应用于每个子集，获得凸包的上半部分和下半部分。

合并两部分

合并从递归中获得的上下半部分，形成最终的凸包。

示例

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
struct Point {
    int x, y;

    // Comparator function to sort points based on polar angle
    static bool compare(Point a, Point b) {
        // Calculate the polar angle of points with respect to the first point
        int orientation = (b.y - a.y) * (b.x - a.x) - (b.x - a.x) * (b.y - a.y);
        
        if (orientation == 0)
            return (a.x + a.y < b.x + b.y);
        
        return (orientation > 0);
    }
};

// Function to find the convex hull using Graham's Scan algorithm
vector<Point> convexHull(vector<Point>& points) {
    int n = points.size();
    
    // Find the point with the lowest y-coordinate (and leftmost if ties)
    int minY = points[0].y, minIndex = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < minY || (points[i].y == minY && points[i].x < points[minIndex].x)) {
            minY = points[i].y;
            minIndex = i;
        }
    }

    // Place the point with the lowest y-coordinate at the beginning
    swap(points[0], points[minIndex]);

    // Sort the remaining points based on polar angle with respect to the first point
    sort(points.begin() + 1, points.end(), Point::compare);

    // Initialize the convex hull with the first three points
    stack<Point> convexHullStack;
    convexHullStack.push(points[0]);
    convexHullStack.push(points[1]);
    convexHullStack.push(points[2]);

    // Process the rest of the points
    for (int i = 3; i < n; i++) {
        // Keep popping the stack while the angle formed by points next to the top is not a left turn
        while (convexHullStack.size() > 1) {
            Point top = convexHullStack.top();
            convexHullStack.pop();
            Point second = convexHullStack.top();

            int orientation = (top.y - second.y) * (points[i].x - second.x) - (top.x - second.x) * (points[i].y - second.y);

            if (orientation > 0) {
                // The angle is a left turn, push the last popped point back
                convexHullStack.push(top);
                break;
            }
        }

        // Push the current point onto the stack
        convexHullStack.push(points[i]);
    }

    // Copy the convex hull points from the stack to a vector
    vector<Point> convexHullPoints;
    while (!convexHullStack.empty()) {
        convexHullPoints.push_back(convexHullStack.top());
        convexHullStack.pop();
    }

    // Reverse the order to get counterclockwise order
    reverse(convexHullPoints.begin(), convexHullPoints.end());

    return convexHullPoints;
}

int main() {
    // Example usage
    vector<Point> points = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};
    
    vector<Point> convexHullPoints = convexHull(points);

    // Display the convex hull points
    cout << "Convex Hull Points:\n";
    for (const Point& p : convexHullPoints) {
        cout << "(" << p.x << ", " << p.y << ")\n";
    }

    return 0;
}

输出

Convex Hull Points:
(0, 0)
(3, 0)
(3, 3)
(0, 3)

解释

#include <iostream>：此行包含输入/输出流头文件，允许程序使用 cout 等函数进行输出。
#include <stack>：此行包含堆栈容器头文件，稍后在代码中使用它来在凸包计算期间维护中间结果。
#include <vector>：此行包含向量容器头文件，提供动态数组功能，用于存储点和凸包。
#include <algorithm>：此行包含算法头文件，用于按极角对点进行排序。
using namespace std;：此行声明代码将使用标准命名空间，避免了在 std:: 前加上 cout 等标准库元素。
struct Point { int x, y; ... };：这定义了一个名为 Point 的结构，表示具有整数坐标 (x, y) 的 2D 点。
static bool compare(Point a, Point b) { ... }: 这是 Point 结构内的静态成员函数。它定义了一个比较器函数，用于根据极角对点进行排序。
int main() {: 主函数，程序执行从这里开始。
vector<Point> points = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};：声明一个 Point 结构向量并用一组 2D 点进行初始化。
vector<Point> convexHullPoints = convexHull(points);：调用 convexHull 函数查找给定点的凸包，并将结果存储在 convexHullPoints 中。
cout << "Convex Hull Points:\n";：输出一条消息，指示以下行将显示凸包点。
for (const Point& p : convexHullPoints) { ... }: 使用基于范围的 for 循环遍历 convexHullPoints 向量中的每个点。
cout << "(" << p.x << ", " << p.y << ")\n";：输出每个凸包点的 x 和 y 坐标。
return 0;: 表示程序成功执行。
}: 关闭 main 函数和程序。
vector<Point> convexHull(vector<Point>& points) { ... }: 定义 convexHull 函数，该函数以点向量为输入并返回表示凸包的向量。
int n = points.size();：获取输入向量中点的数量。
int minY = points[0].y, minIndex = 0;：初始化变量以存储最小 y 坐标和具有最小 y 坐标的点的索引。
for (int i = 1; i < n; i++) { ... }: 遍历点以查找具有最低 y 坐标的点（如果存在平局，则查找最左边的点）。
swap(points[0], points[minIndex]);：将具有最小 y 坐标的点交换到向量的开头。
sort(points.begin() + 1, points.end(), Point::compare);：使用 compare 函数按极角对剩余点进行排序。
stack<Point> convexHullStack;：初始化一个堆栈以在凸包计算期间存储点。
push(points[0]);：将第一个点压入堆栈。
push(points[1]);：将第二个点压入堆栈。
push(points[2]);：将第三个点压入堆栈。
for (int i = 3; i < n; i++) { ... }: 遍历剩余点以构建凸包。
while (convexHullStack.size() > 1) { ... }: 检查并弹出堆栈，直到角度不为左转。
push(points[i]);：将当前点压入堆栈。
vector<Point> convexHullPoints;：初始化一个向量来存储凸包点。
while (!convexHullStack.empty()) { ... }: 将凸包点从堆栈复制到向量。
reverse(convexHullPoints.begin(), convexHullPoints.end());：反转凸包点的顺序以获得逆时针顺序。
return convexHullPoints;: 返回表示凸包点的向量。

凸包算法的应用

凸包算法，包括 Graham 扫描法、QuickHull 和包礼物算法等方法，由于其能够高效地计算点集的凸包，因此在各个领域都有着广泛的应用。凸包作为一种基本的几何构造，在计算机科学、计算几何、机器人技术、图形学、地理信息系统 (GIS) 等领域具有实际意义。在这里，我们探讨了各种应用，它们突出了凸包算法的多功能性和重要性。

1. 计算机图形学：场景渲染和可见性确定

在计算机图形学领域，凸包算法在优化场景渲染和可见性确定方面发挥着关键作用。通过计算场景中 3D 对象的凸包，图形引擎可以有效地剔除不可见的几何体，从而在渲染过程中显著降低计算负载。这种优化对于视频游戏、模拟和虚拟现实等实时应用程序尤其重要，在这些应用程序中，渲染速度至关重要。

凸包通过识别对象的外部边界来促进可见性确定。此信息有助于确定从给定视点可以看到场景的哪些部分，从而使图形引擎能够将渲染工作集中在可见表面上。高效的可见性确定提高了计算机生成环境的整体性能和真实感。

2. 机器人技术：路径规划和避碰

在机器人技术领域，凸包算法在路径规划和避碰方面发挥着举足轻重的作用。通过计算机器人环境中障碍物的凸包，规划器可以定义可用于导航的自由空间。这对于需要在动态变化的环境中导航并同时避免碰撞的自主机器人、无人机和车辆至关重要。

凸包通过提供障碍物的简化表示来促进避碰。与凸包进行实时碰撞检查，使机器人能够快速做出决策以避免潜在的碰撞，从而确保机器人运动的安全性和效率。应用范围涵盖仓库自动化、自动驾驶汽车和机器人手术等领域。

3. 地理信息系统 (GIS)：边界定义和空间分析

在 GIS 应用中，凸包算法有助于边界定义和空间分析。通过计算地理数据点的凸包，GIS 系统可以定义区域的外部边界，从而有助于地块划分和行政边界确定等任务。

凸包也用于空间分析，以简化和分析复杂的空间数据集。例如，在生态研究中，凸包可用于根据观察点勾勒出特定物种的领地或范围。这种空间分析对于栖息地评估、生物多样性研究和野生动物保护工作非常宝贵。

4. 图像处理：对象识别和形状分析

凸包算法在图像处理中找到了对象识别和形状分析的应用。当应用于表示图像中对象的点集时，凸包提供了对象边界的简洁表示。这对于对象识别等任务很有益，其中凸包充当分类对象的区分特征。

在形状分析中，凸包算法有助于量化和描述图像中对象的整体结构。这在医学成像中用于分析解剖形状或在工业环境中用于检查制造组件的形状时特别相关。凸包有助于从图像中提取相关的形状信息，从而有助于图像理解和分析。

5. 计算机辅助设计 (CAD)：用于设计优化的凸包

在CAD 应用中，凸包算法用于设计优化和分析。通过将复杂结构表示为凸包，工程师和设计师可以在保留基本特征的同时简化几何模型。这种简化有助于计算模拟、有限元分析和设计优化过程，从而实现更高效、更流畅的工程工作流程。

结论

凸包算法以其计算包围点集的最小凸多边形的能力，在广泛的行业和技术领域都有应用。从优化图形渲染到增强机器人技术的导航，在 GIS 中定义边界，以及为图像处理中的对象识别做出贡献，凸包算法都提供了基本的几何工具。随着技术的不断进步，凸包算法的应用有望进一步扩展，影响各个学科的创新和解决方案。

下一个主题C++ 中策略模式和状态模式的区别

C++ 凸包算法

揭秘凸包算法的优雅：全面探索

理解凸包问题

凸包算法的类型