平面海量散乱点集凸壳算法  

Algorithm for Convex Hull of Planar Massive Scattered Point Set

作　　者：张忠武[1,2] 吴信才[1] 

机构地区：[1]中国地质大学信息工程学院,武汉430074 [2]佳木斯大学信息电子技术学院,佳木斯154007

出　　处：《计算机工程》2009年第9期43-45,48,共4页Computer Engineering

基　　金：国家“863”计划基金资助项目(2003AA133010);2008-2009年中国地质大学研究生学术探索与创新基金资助项目(CUGYJS0808)

摘　　要：凸壳作为计算几何的一种基本的结构,对GIS的数据分析有着重要作用。在分析传统的凸壳算法的基础上,提出新的凸壳算法,即金字塔算法。同时采用3种快速算法提高执行效率。通过大量实验数据对比说明,算法对求平面海量散乱点集的凸壳非常有效,点集为107数量级的执行时间在主频为2.00 GHz计算机上仅为3 s^4 s。Being a basic structure of computational geometry, convex hull is important to data analysis of GIS. Based on the analysis of traditional convex hull algorithm, a new convex hull algorithm is presented, i.e. pyramid algorithm. It adopts three fast algorithms simultaneously to improve execution efficiency. Comparison of much experiment data shows that the algorithm is very efficient for calculating convex hull of planar massive scattered point set, and for the point set of 107 level, its execution time on a 2.00 GHz personal computer is only three to four seconds.

关 键 词：凸壳 点集 计算几何 地理信息系统 

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