平面点集凸壳的一种快速算法  

An Efficient Algorithm for the Convex Hull of Planar Point Set

作　　者：樊广佺[1] 马丽平[2] 杨炳儒[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083 [2]河北经贸大学计算机中心,河北石家庄050061

出　　处：《地理与地理信息科学》2006年第6期38-41,共4页Geography and Geo-Information Science

基　　金：国家科技成果重点推广项目(2003EC000001)

摘　　要：提出一种计算平面点集凸壳的快速算法———八方向极值快速凸壳算法。该算法首先对平面点集进行一次扫描,从而快速查找到东、南、西、北、东南、西南、东北、西北8个方向上的极值点,构造出一个更接近凸壳的初始凸壳,从而在后续的点集扫描中可以排除更多的内点,使该算法计算效率更高。该算法的空间复杂度为O(N);其时间复杂度虽然无法突破最坏情况下O(NlogN)的理论下限,但其期望时间复杂度已达到线性水平,并且可以容易地扩展到三维和高维空间。This paper presents and realizes an efficient algorithm for the convex hull of planer point set. It is Eight Direction Extreme Value Fast Convex Hull Algorithm. The extreme values on eight directions（east, west, south, north, east - south, west - south, east - north,west- north）are found fleetly after scanning the point set. Thus an initial convex hull that is closer to the real one is built. So more inner points can be excluded during the next scanning. During the second scanning, not only all the inner points of the initial convex hull are excluded,but also every outside point is associated with its unique initial convex hull edge. Thus, the searching of the farthest point is limited in its outside point set. In addition, when a point is judged as an outside point of a sub convex hull edge, the information of the farthest point of the sub convex hull edge is saved, so the distance calculating for searching the farthest point is avoided. All these make the algorithm more efficient. The space complexity of the algorithm is O（N）. Although its time complexity can not break through the low limit of O（Nlog N）in the worst case, its expected time complexity is already linear. Additionally, the algorithm can be generalized to three or high dimension easily.

关 键 词：快速算法 JAVA 凸壳 计算几何 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]