初始顶点八向化凸壳算法

2.2.3　初始顶点八向化凸壳算法

2006年，樊广洤提出对凸壳算法的初始顶点八向化改进。该算法特点是：算法开始时，用很短的时间找到东、西、南、北、东南、西南、东北、西北8个方向上的极值点，构造出一个更接近凸壳的初始凸壳，从而使二维点集S中的90%以上的点成为初始凸壳的内点，这样在后续对点集扫描时就可以排除更多的内点，大大提高该算法的效率。

定义2.1　设S={P_i（x_i，y_i）│1≤i≤m，3≤m＜+∞}为一个平面二维点集，CH（S）是点集S的凸壳，将删除CH（S）上的若干个内部结点后形成的多边形称为点集S的子凸壳（或初始凸壳），记做SCH（S）。

定义2.2　称二维点集S={P_i（x_i，y_i）│1≤i≤m，3≤m＜+∞}的子凸壳上的顶点为子凸壳点，称二维点集S={P_i（x_i，y_i）│1≤i≤m，3≤m＜+∞}的子凸壳上的边为子凸壳边。

定义2.3　如果二维点集S={P_i（x_i，y_i）│1≤i≤m，3≤m＜+∞}中的一个点P位于S的一个子凸壳SCH（S）的外面，则称P为SCH（S）的外点；若点P位于SCH（S）的里面（或在其边上），则称为子凸壳SCH（S）的内点。

定理2.6　二维点集S={P_i（x_i，y_i）│1≤i≤m，3≤m＜+∞}的子凸壳SCH（S）的任一外点只在其一条子凸壳边的外面。

证明：假定定理2.6的结论不成立，即SCH（S）的一个外点P位于两条不同的子凸壳边C_iC_j和C_sC_t的外面。若C_iC_j和C_sC_t平行，由于子凸壳是凸多边形，因此，P就位于凸多边形相对的两条平行线外面。这两条子凸壳边所在的直线将平面划分成不重叠的3个区域：两条直线之间的区域和两条直线外的区域。显然一个点不可能位于两个互不重叠区域内。若C_iC_j和C_sC_t不平行，设其交点为A，则这两条子凸壳边上离A较远的两个凸壳点（设为C_i和C_s）和点P就构成一个三角形，而C_j和C_t必在这个三角形内，即C_j和C_t是内点，这与前面假设的C_j和C_t是凸壳顶点相矛盾，结论得证。

从上述分析可以看出，对于初始凸壳内部的点，只需扫描一次即可被排除。因此，如果能在最短的时间内找到更多的初始凸壳点，会加快整个凸壳的计算速度，使得x=max（x），x=min（x），y=max（y），y= min（y）的点，显然是平面点集S的4个凸壳点。

x_i+y_i= max（x_i+y_i），x_i+y_i= min（x_i+y_i），x_i−y_i= max（x_i−y_i），x_i−y_i= min（x_i−y_i）的点必为凸壳顶点。

证明：如图2.7所示，假设点集S中的点均在平面直角坐标系的第一象限（如果不在可以对S中的点进行平移操作），即x_i≥0且y_i ≥0_，。

（1）设过原点的东南向直线y= −x为L1，点P（x₀，y₀）到直线L1距离为dis t；则：

故到直线L1最远（最近）点，也就是使（x+y）最大（最小）点，且它必为凸壳顶点，因为：其余各点，均在过该点而平行于L1的平行线的同侧。

图2.7　初始顶点八向化凸壳算法示意图

（2）设过无穷远点的东南向直线y=x+b（其中b=+∞）为L2，点P（x₀，y₀）到直线L1距离仍为dis t；则：

同理可证，距离直线L2最远（最近）的点也必为一个凸壳点。

故据定理2.7，可快速找到点集S的正东、正南、正西、正北、东南、东北、西南、西北8个方向上的极值点，便找到更接近于CH（S）的初始凸壳。而要查找8个方向上的极值点，只需在对数据扫描时进行简单快速的加法运算和比较操作，故寻找极值的过程非常迅速（相对于其他运算过程，可忽略不计）。

一、初始顶点八向化凸壳算法描述

第1步：扫描二维点集S={（x_i，y_i）| i=1，2，…，N}中的所有点，分别求出正东、正南、正西、正北、东南、东北、西南、西北这8个方向上的极值点，并分别记为P_max（x）、P_min（y）、P_min（x）、P_max（y）、P_max（x−y）、P_max（x+y）、P_min（x+y）、P_min（x−y），依次连接这8个极值点，将依次连接的每条线段称为子凸壳的边。

第2步：按照图2.7所示的顺序，排列步骤（1）中得到的8个极值点，并去除相邻的重复点（最后一个点和第一个点相邻），构成点集S的初始凸壳。

第3步：扫描二维点集S=｛（x_i，y_i）| i=1，2，…，N｝中除极值点外的所有剩余点。如果该点在某一条子凸壳边的外面，则将该点加入外点集合中，并结束该点对其余子凸壳边的判断。如果该点不是任何一条子凸壳边的外点，则该点为内点，不做任何处理。

第4步：对每一条初始凸壳边做如下处理：

（1）如果该边没有外点则不做任何处理；

（2）如果该边有一个外点，则将该外点直接插入到该初始凸壳边的中间，形成新的初始凸壳，并跳过对这两条新边的处理；

（3）如果该边有两个以上的外点，则求它们到该边的距离并求出距该边最远的点，将其插入到该初始凸壳边的中间，形成新的初始凸壳，并在该边的外点中求出两条新初始凸壳边的外点，从其第一条新初始凸壳边开始处理。

结束步：输出最后所得初始凸壳就是点集S的凸壳CH（S）。

该算法的特点是，在算法开始时，用很短的时间找到东、西、南、北、东南、西南、东北、西北8个方向上的极值点，构造出一个更接近凸壳的初始凸壳，从而使二维点集S中的90%以上的点成为初始凸壳的内点；这样，在后续对点集扫描时就可以排除更多的内点，从而大大提高了该算法的效率。

二、初始顶点八向化凸壳算法分析

1．空间复杂度

设平面点集中有N个点，其凸壳有h个顶点。另外，设最初的初始凸壳多边形的外面有m个点。在该算法中，平面上N个点的坐标存放在一个二维数组（或两个一维数组）中。为了标记一个点是否为凸壳点，需要一个逻辑型的一维数组。另外，还需存储最多h个初始凸壳点的ID号（数组下标）。对于每一条初始凸壳边的外点，只需存储其每一个外点的ID号，并使其与一条初始凸壳边的初始顶点相关联。故该算法只需存储2N个实数，N个逻辑值和h+m个整数。由于h+m≤N，则该算法的空间复杂度为O（N）。

2．时间复杂度

在最好的情况下（即所有点分布在一个矩形区域内），该算法的时间复杂度为O（N−4）。在最坏的情况下（即所有点分布在一个圆周上），该算法的时间复杂度为O（N log N / log 2−4N+8）。因此，在最坏的情况下，该算法也不能突破O（N log N）的时间复杂度下限。

在此，主要分析在一般情况下（点集中的点随机分布在一个圆周内）该算法的时间复杂度。

（1）在对平面点集S中的点进行扫描的过程中，只进行简单的加减运算和线性次数的比较操作，就可以快速确定8个方向上的凸壳点，因此运算速度非常快。在该步骤中，最多可以找到8个初始凸壳点。当然，能找到的初始凸壳点的个数取决于点集S中点的分布状态。

由于第一步查找到的八方向极值点可能有重复，因此要删除相邻的重复初始凸壳点。这时形成的初始凸壳的近似效果较好。在精度要求不高而实效要求苛刻的场合，完全可以作为近似凸壳使用。

（2）对每一个点进行一次判断确定其是否在某条初始凸壳的外侧。根据定理2.6，点集S的子凸壳SCH（S）的一个外点必然只在SCH（S）的一条子凸壳边的外面。因此，已知一个点在某条子凸壳边的外面，即可结束该点对其余子凸壳边的判断，处理下一个点。如果一个点不在任何一条子凸壳边的外面，则为内点。这一步的算法只需要O（N−r）次比较操作，每次比较可在不高于线性的时间内完成（其中N为平面点集S的基数，r为初始凸壳的顶点数）。

（3）由于在圆形区域均匀分布的情况下90%以上的点都被判为内点，使得外点的数量大大减小（一般不到10%）。可以证明，“8个1、8弦与相应圆弧所围成的区域的面积”+“16个1、16弦与相应圆弧所围成的区域面积”+ … ＜ 1/2圆面积。因此，如果点集在圆形区域均匀分布，该步时间复杂度为O（N/2）。

另外，在算法中计算点到直线距离的目的只是为了找到最远点，因此在算法中去掉一些不必要的乘法运算，在一定程度上减少了计算开销。

基于上述原因，使得该算法具有非常高的计算效率。在一般情况下，该算法的期望时间复杂度略低于O（N）。