平面点集的凸包

凸包概念:点集Q的凸包(convex hull)是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
平面凸包的求法：
凸包最常用的凸包算法是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