平面点集凸包Graham算法的改进

摘要：

本文提出了一种计算平面点集最小凸包的快速算法.该算法首先对平面点集进行扫描,查找到最左、最右、最上、最下4个方向上的极值点,以此构造出一个初始凸包,并删除初始凸包内部的所有点;然后把剩余点集分组,每组运用格雷厄姆(Graham)算法生成一个新的凸包;最后将所有子集凸包的顶点看作一个新的点集,再次运用Graham算法生成最终凸包.测试结果表明,改进后的算法可较大幅度地提高执行效率.

关键词：最小凸包、Graham算法、地理信息系统

所属期刊栏目：35

分类号：P282(地图制图学（地图学）)

资助基金：国家基础科学人才培养基金J0630535

在线出版日期：2011-05-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：123-125