10.2 求解凸包问题

简单多边形分凸多边形和凹多边形两类，凸多边形是没有任何“凹陷处”的，而凹多边形至少有一个顶点处于“凹陷处”（称为凹点）。凸多边形上任意两个顶点的连线，都包含在多边形中；凹多边形中总能找到一对顶点，它们的连线有一部分在多边形外。沿着凸多边形周边移动，在每个顶点的转向都是相同的；对于凹多边形，一些是向右转，一些是向左转，在凹点的转向是相反的。图10.12所示的多边形是一个凸多边形，而图10.11所示的多边形是一个凹多边形。

点集 $A$ 的凸包 Convex Hull 是指一个最小凸多边形，满足 $A$ 中的点或者在多边形边上、或者在其内。也就是说，$A$ 点集中任意两点的连线都在其内的点集，就是一个凸包（任意两点的连线都在 $A$ 点集内的点集就是一个凸包）。

图10.13所示的二维平面上有 $10$ 个点，即有这些测试数据：$$\begin{gathered} a_0(4,10),a_1(3,7),a_2(9,7),a_3(3,4),a_4(5,6),a_5(5,4),a_6(6,3), \\ {a}_7(8,1),a_8(3,0),a_9(1,6) \end{gathered}$$ ，其凸包是由点 $a_0,a_2,a_7,a_8,a_9$ 构成的。

求一个点集的凸包，是计算几何的一个基本问题，目前有多种求解算法，这里主要介绍两种求凸包的算法。

10.2.1 礼品包裹算法

这种算法也称卷包裹算法，原理比较简单——先找一个最边缘的点（一般是最左边的点，如果有多个这样的点，则选择最下方的点）。假设有一条绳子，以该点为端点、向右边逆时针旋转、直到碰到另一个点为止，此时找到凸包的一条边；然后用新找到的点作为端点，继续旋转绳子，找到下一个端点；重复这一步骤，直到回到最初的点，此时围成一个凸多边形，所选出的点集就是所要求的凸包。

对于给定的 $n$ 个点 $a[0...n-1]$ ，求解的凸包顶点序列存放在凸包数组 $ch$ 中，其步骤如下：

1. 从所有点中求出最左边的最低点 $a_j$（$x$ 坐标最小者，若有多个这样的点，选其中 $y$ 坐标最小者），置 $tmp=j$ 。
2. 将点编号 $j$ 作为凸包中的一个顶点编号，存放到 $ch$ 中。
3. 对于点 $a_j$ ，找一个点 $a_i$ ，使得 $a_j{a}_i$ 与以 $a_j$ 为起点的水平方向射线的角度最小，如图10.14所示。若存在两个点 $a_i$ 和 $a_k$ ，并有 $a_j,a_i,a_k$ 三点共线，则选取离 $a_j$ 最远的点 $a_i$ ，令 $j=i$ 。确切地说，这里对于点 $a_j$ ，选取的是某个点 $a_i$ ，使得 $a_j{a}_i$ 位于「$a_j$ 与所有其他点的连线」的顺时针方向。emmm……反正自己领悟就是了。
   
4. 对于新的点 $a_j$ ，重复第 $3$ 步。当 $j=tmp$ 时，表示已求出凸包顶点序列 $ch$ ，算法结束。

对于图10.13所示的点集 $a$ ，采用礼品包裹算法求凸包的过程如下：

1. 选取最左边的最下点 $a_9$ 。
2. 当前点为 $a_9$ ，从 $a_9$ 出发，在其余所有点中找到角度最小的点 $a_8$ 。
3. 当前点为 $a_8$ ，从 $a_8$ 出发，在其余所有点中找到角度最小的点 $a_7$ ；
4. 当前点为 $a_7$ ，从 $a_7$ 出发，在其余所有点中找到角度最小的点 $a_2$ ；
5. 当前点为 $a_2$ ，从 $a_2$ 出发，在其余所有点中找到角度最小的点 $a_0$ ；
6. 当前点为 $a_0$ ，从 $a_0$ 出发，在其余所有点中找到角度最小的点 $a_9$ ；
7. 回到起点，算法结束。找到的凸包顶点序列是 $a_9,a_8,a_7,a_2,a_0$ 。
   

采用礼品包裹算法，求解图10.13中凸包的完整程序如下：

#include "Point.cpp"
const int MAXN = 1000;

bool cmp(Point aj, Point ai, Point ak) { 	// 比较两个向量方向的函数
	int d = Direction(aj, ai, ak); 		 	// 调用Direction()
	if (d == 0)								// 共线时,若ajai更长则返回true
		return Distance(aj, ak) < Distance(aj, ai); 
	else if (d > 0)							// ajai在ajak的顺时针方向上,返回true
		return true;
	else 									// 否则返回false
		return false;		
}
// 礼品包裹算法
void Package(vector<Point> a, vector<int> &ch) {
	int i, j = 0, k, tmp;
	for (int i = 1; i < a.size(); ++i)
		if (a[i].x < a[j].x || (a[i].x == a[j].x && a[i].y < a[j].y))
			j = i; 							// 找到最左边的最低点
	tmp = j;								// tmp保存凸包顶点序列的起点
	while (true) {
		k = -1;
		ch.push_back(j);					// 顶点aj作为凸包上的一个点
		for (i = 0; i < a.size(); ++i)      
			if (i != j && (k == -1 || cmp(a[j], a[i], a[k]))) 			
				// 说明ajai与以aj为起点的水平射线的角度小于ajak与其的角度
				k = i;						// 从aj出发找角度最小的点ai
		if (k == tmp) break;				// 找到起点时结束
		j = k;
	}
}
int main() {
	vector<Point> a;
	a.push_back(Point(4, 10));
	a.push_back(Point(3, 7));
	a.push_back(Point(9, 7));
	a.push_back(Point(3, 4));		
	a.push_back(Point(5, 6));
	a.push_back(Point(5, 4));
	a.push_back(Point(6, 3));
	a.push_back(Point(8, 1));
	a.push_back(Point(3, 0));
	a.push_back(Point(1, 6));
	Point st[MAXN];
	vector<int> ch;
	Package(a, ch);
	printf("求解结果\n");
	printf("凸包的顶点: ");
	for (const int &v : ch) printf("%d ", v);
	printf("\n");
	return 0;	
}

运行结果如下所示：

10.2.2 $Graham$ 扫描法

$Graham$ 扫描法（葛立恒扫描法）的原理是，沿逆时针方向通过凸包时，在每个点处应该向左拐，而删除出现右拐的点。可通过设置一个关于候选点的栈 $ch$ 来解决凸包。输入点集 $A$ 中的每个点都进栈一次，非凸包中的顶点最终将出栈，当算法终止时栈中仅包含凸包中的点，其顺序为「各点在边界上出现的、逆时针方向排列」的顺序。

对于给定的 $n$ 个点 $a[0...n-1]$ ，$Graham$ 扫描法求凸包的步骤如下：

1. 从所有点中找到最下且偏左的点 $a[k]$（$y$ 坐标最小者，若有多个这样的点，选其中 $x$ 坐标最小者）。通过交换，将 $a[k]$ 放到 $a[0]$ 中，并置全局变量 $p_0=a[0]$ 。
2. 对 $a$ 中的所有点，按以 $p_0$ 为中心的极角从小到大排序。如图10.15所示，对于两个点 $a_i,a_j$ ，若 $Direction(p_0,a_i,a_j)>0$ ，点 $a_i$ 排在点 $a_j$ 的前面；否则，点 $a_i$ 排在点 $a_j$ 的后面。
   
3. 在点集 $a$ 排序后，先将 $a[0],a[1],a[2]$ 三个点进栈到 $ch$ 中，因为一个凸包至少包含 $3$ 个点。
4. 扫描点集 $a$ 中余下的所有点（从 $i=3$ 开始）。若扫描点 $a[i]$ ，栈顶点为 $ch[top]$ ，次栈顶点为 $ch[top-1]$ ；若有 $Direction(ch[top-1],a[i],ch[top])>0$ ，如图10.16所示，$ch[top-1],ch[top]$ 所成向量在 $ch[top-1],a[i]$ 的逆时针方向，即存在着右拐，则栈顶点 $ch[top]$ 一定不是凸包中的点，将其退栈，如此循环、直到该条件不成立、或栈中少于（等于？）两个元素为止，然后将当前扫描点 $a[i]$ 进栈。
   

对于图10.13所示的点集 $a$ ，采用 $Graham$ 扫描法求凸包的过程如下：

1. 先求出起点 $a_8(3,0)$ ；
2. 按极角从小到大排序后，得到 $a_8(3,0),a_7(8,1),a_6(6,3),a_2(9,7),a_5(5,4),a_4(5,6),a_0(4,10),a_1(3,7),a_3(3,4),a_9(1,6)$ ，如图10.17所示；
   
3. 将 $a_8,a_7,a_6$ 三个点进栈，栈中元素从栈底到栈顶为 $a_8,a_7,a_6$ 。
4. 处理点 $a_2$ ：点 $a_6$ 存在右拐关系（$a_7,a_2,a_6$ 在右手螺旋方向上），将其退栈，如图10.18(a)所示，点 $a_2$ 进栈。栈中元素从栈底到栈顶为 $a_8,a_7,a_2$ 。
5. 处理点 $a_5$ ：$a_7,a_5,a_2$ 在左手螺旋方向上，不存在右拐关系，如图10.18(b)所示，点 $a_5$ 进栈。栈中元素从栈底到栈顶为 $a_8,a_7,a_2,a_5$ 。
6. 处理点 $a_4$ ：点 $a_5$ 存在右拐关系（$a_2,a_4,a_5$ 在右手螺旋方向上），将其退栈，如图10.18 c)所示，点 $a_4$ 进栈。栈中元素从栈底到栈顶为 $a_8,a_7,a_2,a_4$ 。
7. 处理点 $a_0$ ：点 $a_4$ 存在右拐关系（$a_2,a_0,a_4$ 在右手螺旋方向上），将其退栈，如图10.18(d)所示，点 $a_0$ 进栈。栈中元素从栈底到栈顶为 $a_8,a_7,a_2,a_0$ 。
8. 处理点 $a_1$ ：$a_2,a_1,a_0$ 在左手螺旋方向上，不存在右拐关系，如图10.18(e)所示，点 $a_1$ 进栈。栈中元素从栈底到栈顶为 $a_8,a_7,a_2,a_0,a_1$ 。
9. 处理点 $a_3$ ：$a_0,a_3,a_1$ 在左手螺旋方向上，不存在右拐关系，如图10.18(f)所示，点 $a_3$ 进栈。栈中元素从栈底到栈顶为 $a_8,a_7,a_2,a_0,a_1,a_3$ 。
10. 处理点 $a_9$ ：点 $a_3$ 存在右拐关系（$a_1,a_9,a_3$ 在右手螺旋方向上），将其退栈，如图10.18(g)所示；点 $a_1$ 存在右拐关系（$a_0,a_9,a_1$ 在右手螺旋方向上），将其退栈，如图10.18(h)所示；点 $a_9$ 进栈。栈中元素从栈底到栈顶为 $a_8,a_7,a_2,a_0,a_9$ 。
11. 最后求出逆时针方向的凸包为 $a_8(3,0),a_7(8,1),a_2(9,7),a_0(4,10),a_9(1,6)$ 。
    

采用 $Graham$ 扫描法求解图10.13中凸包的完整程序如下：

#include "Point.cpp"
const int MAXN = 1000;
Point p0;									// 起点,全局变量
void swap(Point &x, Point &y) {				// 交换x,y两个点
    Point tmp = x; x = y; y = tmp;
}
bool cmp(Point &a, Point &b) {				// 排序比较关系函数
    return (Direction(p0, a, b) > 0);   	// 如果p0a在p0b的顺时针方向,则返回true,否则返回false
}
int Graham(vector<Point> &a, Point ch[]) {	// 求凸包的Graham算法
    int top = -1, i, k = 0;
    for (i = 1; i < a.size(); ++i)
        if (a[i].y < a[k].y || (a[i].y == a[k].y && a[i].x < a[k].x))
	    	k = i;							// 找最下且偏左的点a[k]
    swap(a[0], a[k]);						// 通过交换将a[k]点指定为起点a[0]
    p0 = a[0];								// 将起点a[0]放入p0中
    sort(a.begin() + 1, a.end(), cmp);		// 按极角从小到大排序
    top++; ch[0] = a[0];
    top++; ch[1] = a[1];
    top++; ch[2] = a[2];
    for (i = 3; i < a.size(); ++i) {		// 判断与其余所有点的关系
    	while (top >= 0 &&					// 准确的说是top>=2,因为栈中至少要有两个顶点
	    	(Direction(ch[top - 1], a[i], ch[top]) > 0 ||
	    	 Direction(ch[top - 1], a[i], ch[top]) == 0 && 
	    	 Distance(ch[top - 1], a[i]) > Distance(ch[top - 1], ch[top]))
		) top--;							// 存在右拐关系,栈顶元素出栈
		top++; ch[top] = a[i];				// 当前点与栈内所有点满足向左关系,进栈
    }
    return top + 1;							// 返回栈中元素个数
}

int main() {
    vector<Point> a;
    a.push_back(Point(4, 10));
    a.push_back(Point(3, 7));
    a.push_back(Point(9, 7));
    a.push_back(Point(3, 4));
    a.push_back(Point(5, 6));
    a.push_back(Point(5, 4));
    a.push_back(Point(6, 3));
    a.push_back(Point(8, 1));
    a.push_back(Point(3, 0));
    a.push_back(Point(1, 6));
    Point st[MAXN];							// 用作栈
    int n = Graham(a, st);
    printf("求解结果\n");
    printf("凸包的顶点:");
    for (int i = 0; i < n; ++i)	{			// 栈中所有元素为凸包
    	st[i].disp();
    	printf(" ");
    }
    printf("\n");
}

运行结果如下所示：

算法分析：对于 $n$ 个点，上述 $Graham(a,ch)$ 算法中排序过程的时间复杂度为 $O(n{\log }_{2}n)$ ，$for$ 循环次数少于 $n$ ，所以整个算法的时间复杂度为 $O(n{\log }_{2}n)$ 。