凸包算法（例如Graham扫描算法或Jarvis步进算法）

凸包算法是一种计算给定点集的凸包的方法。其中，Graham扫描算法和Jarvis步进算法是两种常见且经典的凸包算法。

1. Graham扫描算法：
- 首先，选择一个点作为起始点（通常选择最下方的点，如果存在多个最下方的点，则选择最左边的点）。
- 将其余点按照相对于起始点的极角进行排序（逆时针排序）。
- 依次遍历排序后的点集，对每个点进行如下判断：
- 如果当前点与栈顶的两个点构成的向量形成逆时针转向，将该点入栈。
- 否则，将栈顶的点出栈，直到当前点与栈顶的两个点构成的向量形成逆时针转向，然后将当前点入栈。
- 遍历结束后，栈中剩余的点即为凸包上的点。

2. Jarvis步进算法（也称为Gift Wrapping算法）：
- 首先，选择一个起始点（通常选择最左边的点）作为凸包上的一个点。
- 从起始点开始，依次选择能够使得当前点与下一个点构成的向量形成逆时针转向的下一个点，将其加入凸包。
- 重复上述过程，直到再次回到起始点为止。

这两种算法都是基于极角的思想，通过不断地寻找相邻点之间的逆时针转向来构建凸包。它们的时间复杂度都是O(nh)，其中n是点的个数，h是凸包上的点的个数。相较而言，Graham扫描算法在一般情况下更快一些，但在特殊情况下可能会出现退化，而Jarvis步进算法则相对稳定但效率较低。

相关问题

python 凸包算法

凸包算法是计算给定点集的最小凸多边形的算法。下面介绍两种常见的凸包算法：

1. Graham 扫描算法

Graham 扫描算法是一种基于极角排序的凸包算法。具体步骤如下：

1. 找到点集中 y 坐标最小的点 P0；
2. 将其余点按照与 P0 的极角从小到大排序；
3. 依次将每个点加入凸包中，如果新加入的点使得凸包不再是凸的，则将凸包中不满足凸性质的点删除。

时间复杂度为 O(n log n)。

2. Jarvis 步进法

Jarvis 步进法是一种基于向量叉积的凸包算法。具体步骤如下：

1. 找到点集中最左边的点 P0；
2. 将其余点按照逆时针方向和 P0 的连线与 x 轴的夹角从小到大排序；
3. 从 P0 开始，依次连接与之相邻的点，构成凸包。

时间复杂度为 O(nh)，其中 h 为凸包的点数。在最坏情况下，时间复杂度为 O(n^2)。

需要注意的是，凸包算法的输入点集需要满足不在同一条直线上的任意三个点不共线。如果输入的点集存在共线情况，需要先进行去重等处理。

基于凸包的凹点挖掘算法daima

凸包是指一组点的最小凸多边形包络，而凹点是指在凸包内部和边界上的点，也就是不满足凸的点。凹点挖掘的目标是找到在凸包内部或者边界上的凹点。

基于凸包的凹点挖掘算法包含以下几个步骤：

1. 计算点集的凸包。这一步可以使用Graham扫描、Jarvis步进法等凸包算法。

2. 在凸包上找到起点，从起点开始沿着凸包的边缘前进。遇到凹点则进行保存，在发现拐点（凸点）时检查保存的凹点。如果保存的凹点在拐点两侧，则选择凹度更大的点。

3. 沿着另一条方向继续前进，重复第二步直到回到起点。

4. 处理边界凹点。对于位于边界上的凹点，需要检查相邻的凸点形成的角度是否大于180度。如果大于则说明该凹点是一个有效的凹点。

基于凸包的凹点挖掘算法可以用于处理图形识别、形状描述和计算机视觉等领域。它的优点是计算复杂度较低，对于一般性的数据处理任务具有较高的精度和可靠性。