计算几何中凸包的介绍
在计算几何的研究中，“凸包”的概念是一个基本构件。想象一下在平面上散布的一组点。凸包就像将橡皮筋围绕这些点包裹一样。橡皮筋将形成一个最小的凸多边形，以包围所有散布的点。
理解凸形状
在深入了解凸包之前，理解凸性是什么意思很重要。一个形状是凸的，如果对于形状内部的任意两点，它们之间的线段完全位于形状内。想象一下它就像一个气球。如果你在气球表面的任何地方插入两个针，并用一根线将它们连接起来，线将不会滑出气球。
凸包的定义
一组点的凸包是包围所有点的最小凸集。从数学上看，如果你有一个点集S，那么凸包是包含S的所有凸集的交集。或者，它是采用最小周长包围所有点的边界。
数学表示
一组点S的凸包可以表示为：
Convex hull(S) = { x : x 是 S 中点的凸组合 }
凸包的可视化
例1：基本凸包
考虑一个简单的场景，其中点集只有三个点，形成一个三角形。
在这个例子中，凸包就是三角形本身，因为所有三个点都是它的顶点。
例2：一个更复杂的集
让我们考虑一些更复杂的点：
在这里，这些点形成了一个包含内部点的图形。凸包是一个三角形，排除了(130, 80)的点，因为它不影响包的周长。
凸包的性质
凸性
输出形状总是凸的，即每个内部角度小于或等于180度。
规格
对于给定的一组点，凸包是唯一的。这种唯一性源于凸性定义和欧几里德空间的性质之间没有差别。
最小化
凸包具有包围点集所有点的最小可能边界。
计算凸包的算法
各种算法可以计算一组点的凸包，每个算法具有不同的复杂性和使用场景。以下是一些流行的算法：
礼物包装算法
也称为 Jarvis March 算法，就像沿着形状的边缘移动来包裹礼物。
1. 从集合中最左边的点开始（最小 x 坐标）。 2. 选择与起点形成最小逆时针角的点。 3. 用最近添加的点重复步骤 2，直到返回到起点。
礼物包装的计算复杂度通常为O(nh)，其中n是输入集中的点的数量，h是解决方案中的点数。
Graham 扫描
此算法通过首先对顶点进行排序，然后逐一考虑它们来计算凸包。
1. 找到 y 坐标最低的点，与最小 x 坐标分离。 2. 按增加的顺序排列这些点，它们和步骤 1 中选出的点与 x 轴形成的角度。 3. 重复这些点并移除导致顺时针旋转的点。
其计算复杂度为O(n log n)，主要归因于初始排序操作。
快速凸包算法
快速凸包算法基于分治范式。
1. 找到具有最小和最大 x 坐标的点，这些点应该是凸包的一部分。 2. 使用递归分治过程查找形成每侧定义的线的凸包的点集。
平均复杂度为O(n log n)，而在最坏情况下，它可以是O(n^2)。
增量算法
在此算法中，逐个添加点，并在每一步更新凸包。
1. 从形成初始包的小点集开始。 2. 添加新点并检查它是否位于当前凸包内。 3. 如果它位于外部，则更新凸包以包含新点。
虽然在大 O 符号方面不是最有效的，但此算法在特定应用中仍然具有直观且有用的特点。
凸包的应用
凸包在计算几何及相关领域中有许多实际应用：
计算机图形学
凸包用于计算机图形学中以确定一组对象的边界，以及进行碰撞检测和路径查找。
地理分析
在 GIS 系统中，凸包有助于定义地理单位的边界，如位置组。
模式识别
用于模式识别中，以给点组赋予形状，帮助进行分类和检测。
机器人学
在机器人学中，凸包有助于空间导航和运动规划，并提供绕过障碍物集合的安全路径。
结论
凸包的研究是理解更复杂的计算几何问题的入口。尽管其定义简单，但高效地计算和应用需要对几何和算法设计的深入理解。作为几何的基本方面，凸包仍然是一个活跃的研究领域，并在多种技术应用中扮演着重要角色。
评论