C++ Jarvis March 算法

引言

该算法首先选择一个初始点，通常是最左边的点，作为凸包的起点。然后，它系统地遍历所有点，根据最逆时针的方向选择凸包上的下一个点。这个过程一直持续到凸包闭合，形成包含所有输入点的最小多边形。

Jarvis March 以其简单易懂和易于实现而闻名，使其成为凸包算法的教育和入门课程中的热门选择。然而，其 O(n²) 的二次时间复杂度限制了其在大数据集上的效率，对于计算需求量大的实际应用，更倾向于使用 Graham 扫描或 Chan 算法等更高级的算法。

Jarvis March，也称为“礼品包装”算法，是计算几何学中的一种基本算法，用于查找二维平面上点集的凸包。凸包在计算机图形学、机器人技术和地理信息系统等各种应用中非常重要，在碰撞检测、路径规划和空间分析等任务中起着至关重要的作用。

Jarvis March 算法的主要目标是高效地确定包围给定点集的最小凸多边形。凸包被定义为包含所有输入点的最小凸多边形，Jarvis March 算法通过系统地迭代选择凸包上的点来实现这一点。

历史背景

Jarvis March 算法，通常称为礼品包装算法，是计算几何领域的一项重要算法。它由 R. A. Jarvis 于 1973 年推出，此后成为查找二维平面上点集凸包的基本方法。了解 Jarvis March 算法的历史可以深入了解其发展、应用及其在计算几何领域的持久意义。

R. A. Jarvis 与算法的诞生

澳大利亚计算机科学家 Rolf Arvid Jarvis 被认为是 1973 年推出了礼品包装算法。当时，计算几何学作为计算机科学的一个独立领域正在兴起，研究人员正在探索用于高效解决几何问题的算法。Jarvis 设计该算法是为了解决凸包查找这一基本问题，凸包是计算几何学中的一个基本概念，在各个领域都有应用。

动机和早期应用

开发 Jarvis March 算法的主要动机是提供一种简单直观的方法来查找点集的凸包。凸包在计算机图形学、机器人技术、地理信息系统以及众多其他领域至关重要，在这些领域，空间关系和高效算法至关重要。

Jarvis March 特别适合教育目的，并作为向学生介绍计算几何学基本概念的起点。它的简单性使其成为学习者掌握方向、凸性和几何问题解决等基本概念的易于理解的算法。

礼品包装的比喻

该算法因其与用丝带包装礼物的过程直观相似而获得“礼品包装”的绰号。就像丝带围绕礼物系统地缠绕一样，该算法围绕点集进行包装以构建凸包。这种类比有助于理解算法选择凸包上点的迭代和系统方法。

初步反响和认可

Jarvis March 因其简单性而获得认可，无论是在理解还是实现方面。其直观的性质使其成为宝贵的教学工具，为学生提供了解决几何问题的实践经验。随着该算法的简单性得到广泛认可，它开始在教育领域之外找到应用。

局限性和进展

虽然 Jarvis March 有其优点，但并非没有局限性。其二次时间复杂度 O(n²)，其中 n 是输入点的数量，意味着其效率在大数据集上会显着下降。随着计算几何学的不断发展，研究人员寻求具有更好时间复杂度的更高级算法，以处理更大、更复杂的数据集。

遗产和持续相关性

尽管存在局限性，Jarvis March 算法仍然是计算几何学中的基础概念。它为开发更复杂的凸包算法铺平了道路，这些算法解决了大数据集带来的挑战。尽管 Graham 扫描和 Chan 算法等算法在实际应用中变得更加普遍，但 Jarvis March 仍被作为凸包问题和几何算法的入门而被研究和教授。

总之，Jarvis March 算法的历史与计算几何学作为一门学科的成长息息相关。R. A. Jarvis 于 1973 年的贡献标志着一个重要的里程碑，提供了一种简单有效的方法来解决凸包问题。该算法的遗产不仅在于其历史意义，还在于它作为学习者和研究者探索计算几何学丰富领域的一个垫脚石。

关键概念和过程

Jarvis March 算法的特点是其简单易懂和易于实现。该算法的基本思想可总结为以下步骤：

初始化

选择最左边的点作为凸包构建的起始点。如果有多个最左边的点，则选择 y 坐标最低的点。

凸包构建

• 从起始点开始，迭代选择凸包上的下一个点。
• 对于每个当前点，考虑所有其他点，找到与当前点具有最逆时针方向的点。
• 具有最逆时针方向的点将成为凸包上的下一个点。
• 重复此过程，直到凸包闭合，并且再次到达起始点。

终止

• 当再次到达起始点并且凸包闭合时，算法终止。

用例

• 教育目的
  计算几何学入门：Jarvis March 通常用作入门算法，用于教授计算几何学的基本概念。它的简单性使其成为学生理解凸包问题和基本几何算法的理想起点。
• 小到中等规模的数据集
  简单的实现：Jarvis March 的直接性使其适用于小到中等规模的数据集。在点数不多的情况下，该算法提供了简单直观的凸包查找解决方案。
• 基准测试和比较
  性能评估：Jarvis March 可以作为基准，用于比较更高级凸包算法的性能。虽然它可能不是处理大型数据集最高效的算法，但将其性能与其他算法进行比较有助于研究人员和从业人员理解选择特定算法所涉及的权衡。
• 教授算法概念
  理解循环结构：Jarvis March 的嵌套循环结构有利于教授算法概念，如嵌套迭代和条件语句。学生可以了解点方向如何用于构建凸包。
• 计算资源较低的情况
  低开销：在计算资源有限且简单解决方案足够的情况下，Jarvis March 可以是一个可行的选择。其较低的空间复杂度使其适用于内存受限的环境。

注意事项

• 二次时间复杂度
  大型数据集的局限性：Jarvis March 的主要缺点是其二次时间复杂度 O(n²)。随着输入点数量的增加，算法的性能会显着下降。对于大型数据集，通常更倾向于使用 Graham 扫描或 Chan 算法等更高效的算法，因为它们具有更好的时间复杂度。
• 大型数据集的更好替代方案
  Graham 扫描和 Chan 算法：在处理大型数据集时，具有更好时间复杂度的凸包算法变得更加理想。Graham 扫描和 Chan 算法的时间复杂度为 O(n log n)，性能优于 Jarvis March，并且在实践中通常因效率而受到选择。
• 退化情况和共线点
  处理共线点：Jarvis March 在处理大量共线点的.集时可能会效率低下。在数据集沿直线排列或包含共线点的情况下，该算法可能需要访问比必需更多的点，从而导致额外的计算和潜在的效率低下。
• 数值稳定性
  浮点精度：与许多几何算法一样，Jarvis March 涉及浮点计算。数值稳定性可能是一个问题，尤其是在处理精度有限的.数据时。实现者需要考虑与浮点算术和舍入误差相关的问题。
• 确定性输出
  非唯一性：Jarvis March 生成的凸包可能不是唯一的，特别是在有多个点与当前点具有相同角度的情况下。共线点的选择顺序会影响最终的凸包。用户应该意识到输出中的这种非唯一性。
• 适应问题特性
  特定于问题的考虑：凸包算法的选择取决于特定问题的特性。虽然 Jarvis March 可能适用于某些情况，但应考虑数据的性质和问题的要求。例如，在只需要快速简单解决方案的情况下，尽管 Jarvis March 具有二次时间复杂度，但也可能选择它。
• 算法进展
  探索高级算法：随着计算资源和算法理解的进步，研究人员和从业人员可能会探索更高级的凸包算法。虽然 Jarvis March 提供了基础知识，但它可能不是需要高性能凸包计算的前沿应用的最佳选择。

总之，Jarvis March 是一种有价值的算法，具有特定的用例，尤其是在教育环境和数据集较小到中等规模的情况下。然而，其在时间复杂度和处理某些数据集特性方面的局限性使其不太适合大规模和复杂应用。用户和实现者在决定是采用 Jarvis March 还是根据其应用的具体要求选择更高级的凸包算法时，应考虑这些用例和注意事项。

示例

下面是 C++ 中 Jarvis March 算法的程序

输出

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

解释

1. #include <iostream>: 包含输入/输出流头文件，用于标准 C++ 输入/输出操作。
2. #include <vector>: 包含 vector 头文件，用于在 C++ 中使用 vector 容器。
3. #include <algorithm>: 包含 algorithm 头文件，用于使用 std::sort 等算法。
4. struct Point { int x, y; };: 定义一个名为 Point 的结构体，用于表示具有 x 和 y 坐标的 2D 点。
5. int orientation(Point p, Point q, Point r) { ... }: 定义一个函数，用于计算三个点的方向（顺时针、逆时针或共线）。
6. void convexHullJarvis(std::vector<Point>& points) { ... }: 定义实现 Jarvis March 算法以查找点集凸包的主要函数。
7. int n = points.size();: 获取输入 vector 中的点数。
8. if (n < 3) { std::cerr << "Convex hull not possible with less than 3 points." << std::endl; return; }: 检查是否至少有 3 个点可以构成凸包；否则，打印错误消息并返回。
9. std::vector<Point> convexHull;: 创建一个空 vector 来存储凸包点。
10. int leftmost = 0; for (int i = 1; i < n; i++) { if (points[i].x < points[leftmost].x) { leftmost = i; } }: 查找最左边的点作为凸包构建的起始点。
11. int p = leftmost, q; do { ... } while (p != leftmost);: 初始化变量 p 和 q 分别表示凸包上的当前点和下一个点，然后迭代直到再次到达起始点。
12. convexHull.push_back(points[p]);: 将当前点 p 添加到凸包中。
13. q = (p + 1) % n;: 以循环方式更新下一个点 q。
14. for (int i = 0; i < n; i++) { if (orientation(points[p], points[i], points[q]) == 2) { q = i; } }: 通过遍历所有点并选择方向最逆时的点来查找凸包上的下一个点。
15. p = q;: 为下一次迭代更新当前点。
16. std::cout << "Convex Hull Points:" << std::endl; for (const Point& point : convexHull) { std::cout << "(" << point.x << ", " << point.y << ")" << std::endl; }: 打印凸包点。
17. int main() { ... }: 提供示例用法的 main 函数。
18. return 0;: 返回 0 表示程序成功执行。

时间和空间复杂度分析

Jarvis March 算法的时间和空间复杂度分析涉及理解算法在时间需求和内存使用方面的表现。

时间复杂度分析

Jarvis March 算法的时间复杂度主要取决于查找凸包上每个点所做的比较次数。我们用 n 表示输入集中的点数。

查找最左边的点

• 查找最左边点的循环需要 O(n) 时间，因为它只遍历所有 n 个点一次。

构建凸包

• 外层循环运行 n 次，因为每次迭代都会向凸包添加一个点。
• 内层循环，用于搜索凸包上的下一个点，在最坏情况下最多可以有 n 次迭代。
• 凸包构建的总体时间复杂度为 O(n²)。

总时间复杂度

• 查找最左边点的时间复杂度为 O(n)。
• 构建凸包的时间复杂度为 O(n²)。

因此，Jarvis March 算法的总体时间复杂度为 O(n+n²) = O(n²)。二次时间复杂度源于用于通过重复选择基于当前点方向的下一个点来查找凸包点的嵌套循环。

空间复杂度分析

Jarvis March 算法的空间复杂度受存储输入点所需的空间以及用于凸包的空间的影响。

输入点

• 输入点 vector 由 n 个 Point 结构表示，每个结构包含两个整数 (x, y)。
• 存储输入点的空间复杂度为 O(n)。

凸包点

• 凸包由另一个 Point 结构 vector 表示，该 vector 存储凸包上的点。
• 最坏情况下，存储凸包点的空间复杂度也为 O(n)，因为所有点都可能成为凸包的一部分。

附加空间

• 该算法使用一些额外的变量，如索引 (p, q)，但这些变量需要恒定空间，并且对总体空间复杂度没有显着贡献。

总空间复杂度

• 存储输入点的空间复杂度为 O(n)。
• 存储凸包点的空间复杂度为 O(n)。
• Jarvis March 算法的总体空间复杂度为 O(n+n) = O(n)。

总结

• 时间复杂度：Jarvis March 算法的时间复杂度为 O(n²)，其中 n 是输入点的数量。用于查找凸包点的嵌套循环结构是导致二次时间复杂度的主要因素。
• 空间复杂度：Jarvis March 算法的空间复杂度为 O(n)，其中 n 是输入点的数量。此复杂度源于存储输入点和凸包点所需的空间。该算法的空间需求随输入大小线性增长。

在实践中，Jarvis March 算法适用于小到中等规模的数据集，但其二次时间复杂度使其对于非常大的数据集效率不高。其他凸包算法，例如 Graham 扫描或 Chan 算法，旨在为大型数据集实现更好的时间复杂度。