2.2.4 初始顶点四角化凸壳算法
2002年，刘润涛对凸壳算法提出初始顶点四角化改进。类似于初始顶点八向化凸壳算法，该算法另采用“四角化”来找到凸壳初始顶点，并对原二维点集进行预处理，以尽可能地缩小凸壳寻找点的总数，减少算法的时间复杂度，示意图如图2-8所示。
图2.8 初始顶点四角化凸壳算法示意图
定义2.4 设Pi=（xi，yi），i=1，2，…，n；是给定的多边形的n个顶点，若对于该给定多边形的任意两边的线段或是相邻且相交与一个端点或者不相交，则称该多边形为简单多边形。
定义2.5 对于简单多边形P，设它的端点顺次为P1，P2，…，Pn，Pn+1。若沿P1，P2，P3，…，Pn，方向走，该简单多边形的有界区域总在左边，则称该多边形是逆时针多边形；若沿着Pn，Pn−1，Pn−2，…，P1这样的方向走，该简单多边形的有界区域总在右边，则称该多边形是顺时针多边形。
定义2.6 设二维点集上任意三个点Pi（i=1，2，3）的坐标为Pi=（xi，yi），存在行列式函数：
满足：
（1）12332121232f(P,P,P)(xx)(yy)(xx)(yy)=−−−−−，但不是唯一的。
（2）P1，P2，P3三点共线的充分必要条件是f（P1，P2，P3）
=0。
（3）P2位于直线P1，P3右侧的充分必要条件是f（P1，P2，P3）＆gt;0；反之，P2位于直线P1，P3左侧的充分必要条件是f（P1，P2，P3）＜0。
一、初始顶点四角化凸壳算法描述
（1）X坐标为xmin的Y坐标值最大点，记为M1，其点列的下标为k1；X坐标为xmin的Y坐标值最小点，记为M8，其点列的下标为k8。
（2）X坐标为xmax的Y坐标值最大点，记为M4，其点列的下标为k4；X坐标为xmax的Y坐标值最小点，记为M5，其点列的下标为k5。
（3）Y坐标等于ymin中X坐标值最大的点，记为M6，其在点列中的下标为k6；Y坐标等于ymin中X坐标值最小的点，记为M7，其在点列中的下标为k7。
（4）Y坐标等于ymax中x坐标值最大的点，记为M3，其在点列中的下标为k3；Y坐标等于ymax中x坐标值最小的点，记为M2，其在点列中的下标为k2。
如图2.8所示，根据点集凸壳及简单多边形的定义可知：线段M8M1，M2M3，M4M5及M6M7为凸壳的边，而位于简单多边形M1M2M3 M4M5M6 M7M8内的各点均非凸壳顶点，故不予考虑。这样，凸壳其余顶点只会在图中矩形域四角的三角形PLUM1M2，PLDM7M8，PRDM5M6，PRUM3M4中（含其边）。因这四个三角形内的子点列具有相同拓扑结构，故只需讨论一个子点列（例如三角形PLUM1M2中的点列）的处理即可。
若线段M1M2外侧没有点，则线段M1M2已为凸壳的一条边。
若线段M1M2外侧有n个点，则这些点中能够成为凸壳顶点的点必在三角形PLUM1M2中，故应对此三角形区域中各点Pi处理如下：
若yPi≤yM1或xPi≥xM2，则Pi点一定不能落入三角形PLUM1M2中，故不可能为凸壳上的点；否则（即yPi＆gt;yM1且xPi＜xM2），Pi点一定在三角形PLUM1M2中，故应继续作如下处理：
假定P1点为凸壳顶点，取另外一个点P2，则P1点和P2点的位置关系为：
当xP2＜xp1时，若yP2＆gt;yp1，则P1不可能为凸壳顶点，用P2代替P1；否则，P2不可能为凸壳顶点。
当xP1＜xp2＜xM2时，可由f（M1，P1，P2）的正负性判断P2是否能成为凸壳上的点：
若f(M1,P1,P2)≥0，则说明P2位于M1P1之左侧或之上，P1不可能为凸壳上的点，以P2代替P1。
若f(M1,P1,P2)＜0则说明P2位于M1P1之右侧。此时，若yP2＜yp1，则P2亦可能为凸壳上的点，将P2加入凸壳点列。
当xP2＜xp1时，若f(M1,P1,P2)＆gt;0，则说明P2位于M1P1之左侧，P1不可能为凸壳上的点，以P2代替P1；若f(M1,P1,P2)＜0，则说明P2位于M1P1之右侧或之上，不可能为凸壳上的点。
假设已对i=3，4，…，k进行了如上的判断过程，现欲考虑Pk+1。顺序取出两个点记为r1和r2（即r1为当前最新找到的凸壳上的点）。则Pk+1的位置关系按如下情况判断：
当xPk+1=xr1时，若yPk+1=yr1，则r1不可能为凸壳上的点，再顺序取出两个点，仍然记为r1和r2。
若f(r2,r1,pk+1)≥0，则表明Pk+1在r1 r2之左侧，r1不可能为凸壳上的点。
重复这个过程直到找到了r1和r2，使f(r2,r1,Pk+1)＜0或r1= M1（此时，只有M1和Pk+1为凸壳上的点）。
当yPk+1≤yr1时，Pk+1不可能为凸壳上的点。
当xr1＜xpk+1＜xM2时，若f(r2,r1,Pk+1)≥0，则r1不可能是凸壳上的点，再顺序取出两个点分别记为r1和r2。若f(r2,r1,Pk+1)≥0重复这个操作，直至f(r2,r1,Pk+1)＜0或r1=M1。
当f(r2,r1,Pk+1)＜0时，若yPk+1≤yr1，则pk+1不可能为凸壳上的点。若yPk+1＆gt;yr1，则Pk+1为凸壳上的点。
当xr1＆gt;xpk+1时，若f(r2,r1,Pk+1)＆gt;0，则Pk+1位于r 1 r2之左侧。
在点集中顺序中查找，从二维点集中顺序取出两个点r1和r2。若f(r2,r1,Pk+1)≥0，则删除r1，再从二维点集中顺序取出两个点r1和r2。重复以上的过程，直至f(r2,r1,Pk+1)＜0或r1=M1。
若f(r2,r1,Pk+1)≤0时，说明Pk+1位于r1 r2之右侧或之上。由于所考虑的问题是个简单多边形，故Pk+1不可能位于其他凸壳点顺序连线的左侧，否则，最新的凸壳上的点与Pk+1的连线就与简单多边形的多边相交，与简单多边形的定义相矛盾。
通过以上各种情况的分析，最后可得到该子点列中所有的凸壳顶点。
同理，对其余3个子点列可仿上述过程作处理，把所得子点列的凸壳顶点相连，就得到整个简单多边形的凸壳顶点，亦即得到所求凸壳。
二、初始顶点四角化凸壳算法分析
通过计算，可以得出：该算法的时间复杂度至多需要4（n−4）次乘法，6（n−4）次减法，及12n−4+5n−12+4=17n−12次比较运算；而其空间复杂度不超过2n。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
