2009年9月

第23卷第3期总77期北京联合大学学报(自然科学版)

JournalofBeijingUnionUniversity(NaturalSciences)Sep.2009

Vol.23No.3SumNo.77

GIS中散乱点集凸包的快速算法及编程

李军辉,李紫阳

1

2

(1.东南大学交通学院,南京 210096;2.沈阳军区某部司令部,沈阳 110000)

[摘 要] 在地理信息系统(GIS)中,(。通过研究了传统凸包算法,并对其进行改进,提出简单快速的点集凸包改进算法。经过验证,新算法可准确快速地求出点集凸包。[关键词] GIS;凸包;算法;编程

[中图分类号] P208 [文献标识码] A [文章编号] 1005-0310(2009)03-0032-03

AQuickAlgorithmandProgrammingtoDetermineConvexHull

forPlanarScatteredPointSetinGIS

LIJun-hui,LIZ-iyang

1

2

(1.TransportationCollege,SoutheastUniversity,Nanjing 210096,China;

2.ShenyangMilitaryRegionCommand,Shenyang 110000,China)

Abstract:InGIS,theconvexhullalgorithmsofapointsetarealwaysappliedinthegenerationofTINandthebuildingofDTM.Thepaperdiscussesthetraditionalconvexhullalgorithmsandputsforwardafasteralgorithm.Ithasbeenprovedthatthenewalgorithmcanacquireconvexhullquicklyandaccurately.

Keywords:GIS;convexhull;algorithm;programming 在地理信息系统(GeograghicInformationSystem,GIS)应用中,原始数据经常是一些离散数据,比如雨量分布数据等,由于数据的采集、传输和录入的顺序不同,一般是一些散乱的数据记录,称其为散乱点集。

凸包问题是计算几何中一个重要问题,在GIS中,动态计算面积、裁剪区域、生成TIN及DTM都需要用到散乱点集的凸包算法。

本文综合各种凸包求取算法,对算法进行改进并在VC++610环境中编程实现,实验证明本文算法可有效快速地求出点集凸包。

[1]

描法等。增量法首先取几个点,形成初始凸包,然后不断寻找当前凸包外的新顶点来更新凸包,直到所有的点都在凸包内。该算法的计算复杂度为O(n)。格雷厄姆扫描法首先找到最小y坐标点,接着按照其它点和该极值点的连线与x轴的夹角的角度值排序,通过判断连续3个点的空间关系,从而得到逆时针排列的凸包顶点,其计算复杂度为O(nlogn)

[3-5]

2

[2]

。

在传统的算法中,所有的点都参加运算,增加了运算所需要的时间。Yao证明凸包算法的计算复杂度下限为O(nlogn)

[6]

。而本文采用了一种改进

1 算法复杂度分析

上世纪70年代以来,不少学者提出了点集凸包的计算方法,较为经典的有增量法、格雷厄姆扫

[收稿日期] 2009-06-16

的快速凸包求取思路。找到一个凸包的边界,这个边界被真正的凸包所包围,而凸包的大部分点都在这个边界的内部,将边界内部的点删除,这样运算

复杂度将远远小于O(nlogn)。

[作者简介] 李军辉(1981)),男,山东潍坊人,南京市东南大学学生,硕士研究生,主要研究方向为地图制图学与地理信息工程。