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

编号 zgly0001608140

文献类型 期刊论文

文献题名 平面点集凸壳的一种快速算法

作者 樊广佺  马丽平  杨炳儒 

作者单位 北京科技大学信息工程学院  河北经贸大学计算机中心  北京科技大学信息工程学院北京100083  河北石家庄050061  北京100083 

母体文献 地理与地理信息科学 

年卷期 2006年06期

年份 2006 

分类号 TP301.6 

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

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