文献类型：期刊文章

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

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

出　　处：《地理与地理信息科学》

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

年　　份：2006

卷　　号：22

期　　号：6

起止页码：38-41

语　　种：中文

收录情况：BDHX、BDHX2004、CSCD、CSCD2011_2012、JST、NSSD、RCCSE、RWSKHX、ZGKJHX、核心刊

摘　　要：提出一种计算平面点集凸壳的快速算法———八方向极值快速凸壳算法。该算法首先对平面点集进行一次扫描,从而快速查找到东、南、西、北、东南、西南、东北、西北8个方向上的极值点,构造出一个更接近凸壳的初始凸壳,从而在后续的点集扫描中可以排除更多的内点,使该算法计算效率更高。该算法的空间复杂度为O(N);其时间复杂度虽然无法突破最坏情况下O(NlogN)的理论下限,但其期望时间复杂度已达到线性水平,并且可以容易地扩展到三维和高维空间。

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

分 类 号：TP301.6]