凸包及其应用

概念 　　

   1.1 点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。

　　1.2 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了。

平面凸包的求法

　　2.1　凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。

　　对于一个有三个或以上点的点集Q，过程如下：

　　计算点集最右边的点为凸包的顶点的起点，如上图的P3点。

　　Do

　　For i = 0 To 总顶点数

　　计算有向向量P3->Pi

　　If 其余顶点全部在有向向量P3->Pi的左侧或右侧，则Pi点为凸包的下一顶点

　　Pi点加入凸包列表

　　GoTo 1

　　End If

　　Next

　　Exit Do

　　1: 　

 　Loop

　

 　此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。

　 　2.2　求凸包有很多方法，不过最适合OI的估计还是Graham's Scan这个方法了。它的大致方法是这样的： 首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极角（atan2(y-y0,x-x0)），并按照极角对这些点排序，前述基准点在最前面，设这些点为P[0]..P[n-1]；建立一个栈，初始时P[0]、P[1]、P[2]进栈，对于P[3..n-1]的每个点，若栈顶的两个点与它不构成“向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凸包了。 　

 　如何判断A、B、C构成的关系不是向左转呢？如果b-a与c-a的叉乘小于0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x。