凸包graham算法

Graham-Scan算法是一种灵活的凸包算法，时间复杂度是O(nlogn)。该算法的基本理念是：初始化将包含凸包点的空堆栈。选择一个起点并将其添加到堆栈中。围绕起点到其余点做极角，按逆时针顺序对其余点进行排序。扫描排序的点。用叉积判断新点和栈顶头两个点形成的拐向。顺时针就弹出栈顶元素，继续判断。否则逆时针压入新点p[i]最初将每个新点添加到堆栈中，然后检查以确保新点的外壳仍然是凸的。删除任何创建凹角的点 - 这些点位于船体内部。最终栈内元素就是凸包点。

相关问题

凸包填充算法 matlab

凸包填充算法是一种在数字图像处理中常用的算法，也可以在MATLAB中实现。算法的基本思想是利用图像中各像素点的位置信息，判断其是否属于图形的凸包，从而将凸包内的像素点填充为指定的颜色。

在MATLAB中，可以使用以下步骤实现凸包填充算法：

1. 读入图像并将其转换为二值图像，即只有黑白两种颜色。

2. 对于二值图像中的每一个像素点，利用某种方式判断其是否在凸包内。这可以使用Andrew的凸包算法、Graham的凸包算法等方法来实现。对于每个点，通过遍历所有边界点，判断是否在所有边界点的左侧或右侧，从而判断其是否在凸包内。

3. 利用内置的MATLAB函数fill函数将凸包内的像素点填充为指定的颜色。该函数可以接受一个表示凸包内像素点坐标的矩阵作为输入。

4. 最后，将填充后的图像显示出来。

需要注意的是，由于凸包填充算法基于凸包的概念，因此它只适用于凸多边形的填充。如果图形包含非凸点、内凹点等，则需要进行额外的处理。

总体来说，凸包填充算法在MATLAB中的实现相对简单，可以通过判断像素点位置、填充像素点等步骤来完成。这种算法在图像处理领域有着广泛的应用，可以用于实现形状的填充、分割等操作。

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)。

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