凸包算法（例如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)。

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