[数据结构与算法]计算几何-寻找凸包

问题定义

一个点集$\Sigma$的凸包是一个面积最小的凸多边形$P$，满足点集中每个节点都在P的边界或者P的内部。

显然，凸包中每个顶点都是点集中的点。

主要方法

• 增量法（Incremental method），对点集进行从左到右排序，在第$i$步中，根据前$i$个节点形成是的凸包对第i个节点进行考察，是否加入p中。时间复杂度为$O(n\lg n)$
• 分治法，将点集分为最左边$\frac{n}{2}$个节点和最右边$\frac{n}{2}$节点，分别对这两部分进行递归计算。然后使用一种$O(n)$的方法进行合并。$T(n)=2T(\frac{n}{2})+O(n)$可以得到$T(n)=O(n\lg n)$
• 剪枝搜索。
• 旋转扫除法，下面介绍的两种算法都是采用的该种方法。该方法通过类似旋转的过程，每次逐步完成凸包的构建。

Graham扫描法

它是按照以下流程进行的：

1. 选择纵坐标最小的节点作为基准点$p_0$（如果存在多个则选择横坐标最小的点）
2. 根据$p_0$对剩下的所有节点按照和$p_0$的极角进行排序。
3. 将$p_0,和排序后的p_1,p_2$加入一个栈内。
4. 考察第$i$个节点$p_i$，如果该节点和栈中的栈顶$l_0$，栈次顶$l_1$构成一个左转，那么将$p_i$加入栈中，否则删除节点$l_0$，然后重复操作4，直到满足前一条件，或者栈中元素少于2.
5. 程序结束，栈中元素即是凸包的逆时针序列。

Javis步进法

• 该算法的主要思路即每次寻找极角最小的点作为凸包。

1. 寻找和Graham一样的$p_0$点。
2. 以该点为基准点，寻找极角最小的点，并以该节点为新的基准点重复步骤2.
3. 如果步骤2发现的新的基准点为$p_0$则结束循环。步骤2中发现的基准点即为凸包。

==对于极角的比较，以及是否左转用到的都是点的叉乘，参见点的叉乘

备注：文中所有图片出自《算法导论》