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

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)),男,山东潍坊人,南京市东南大学学生,硕士研究生,主要研究方向为地图制图学与地理信息工程。

第23卷第3期李军辉等:GIS中散乱点集凸包的快速算法及编程

33

min和x

-

2 凸包算法描述

211 相关定义

定义1:设P=(x,y,1)为平面内任一点,计算P与AB的点积,可得点与直线的位置判断函数:

F(P,AB)=(x,y,1)

(yA-yB,xB-xA,xA#yB-xB#yA)=(yA-yB)#x+(xB-xA)#y

+(xA#yB-xB#yA)

根据F的正负号可以判断P与AB的相对位置关系,如图1所示。

1)如果F>0,P在AB的左半平面内;2)如果F=0,P在AB所在的直线上;3)如果F<0,P在AB

的右半平面内。

大最小的两个点x

-

max。

步骤3:,比较好的一个小区间的宽度选择为w=x

--

intervalP(2n)

1

[7]

。其中x

interval=x

-

max-x-min。

步骤4:找到各个区间中y方向上的两个极值点k[i]1miny和k[i]1maxy。

步骤5:把各个区间中的极值点按照顺序连接起来,如图3所示,首先按照i大小的次序依次连接k[i]1miny,同理连接k[i]1maxy。最后连接xmin和k[0]1miny、x

--

min和k[0]1maxy、x

-

max

和k[m-1]1miny、x-max和k[m-1]1maxy,构成一个封闭的多边形,即前文提到的边界。

图1 P与AB相对位置关系

定义2:采用矢量叉积法判断连续的三矢量顶点的凹凸性,如图2所示

:

图3 边界构成示意图

图2 点的凹凸性判断

步骤6:根据定义1依次判断输入的点是否在边界内部并删除边界内部的点。

步骤7:在平面的离散点集中选择y坐标最小的点,如有相同最小y坐标的点,则选择其中x坐标最小点记为P0。

步骤8:以P0为起点与其它所有点构成矢量P0P1,P0P2,,,P0Pn-1,步骤9:按角度排序所有点,构成一个逆时针顺序的数据结构,作为一个有序的序列。

步骤10:保留同一矢量方向上振幅最大的矢量端点,其余矢量端点删除。

步骤11:根据定义2采判断连续的三矢量顶点的凹凸性。

步骤12:删除所有凹点,所有保留的离散点集即为凸包的子集。

以Vi为其任一顶点,Vi+1和Vi-1为其前后相邻顶点,作矢量叉积:

T=Vi-1Vi@ViVi+1。

取T的z坐标分量,可得点的凹凸性判断函数:

S(Vi,Vi+1,Vi-1)=(xi-xi-1)@(yi+1-yi)-(xi+1-xi)@(yi-yi-1) 根据S的正负号可以判断点Vi的凹凸性。

1)如果S>0,Vi为凸点;2)如果S=0,Vi为中性点;3)如果S<0,Vi为凹点。212 凸包算法描述

算法步骤:

步骤1:读取离散点集的数据坐标及个数n。

,

34

北京联合大学学报(自然科学版)2009年9月

3 程序设计

311 编程环境

本程序用VC++610来实现,可以在Win-dows98P2000Pxp为操作平台的计算机上运行,并在机器上调试通过。

312 数据结构

为了提高算法的执行效率和节约内存,本文的算法引入了数据结构。

1)有序点表 用于保存散乱点和排序后的点序列,表中每个元素的结构为:

typedefstruct{ doublex;

doubley; PP点的坐标 doublearCos; PP点的余弦值}Point;

2)存储器定义 用于存储点集分块之后的信息的类型实例,表中每个元素的结构为:

typedefstruct{

intpoint-index[MAXN];PP点属于的区间 intmember-count;PP点数 intminy,maxy;PP区间最大最小值

inttag;PP点的余切值

}Point-memo;313 凸包算法程序设计

程序输入:平面上n个点P1,P2,,,Pn的坐标(xi,yi)。

程序输出:点集凸包顶点。程序流程图如图4所示:

4 运行结果

用随机实数生成函数产生范围为(0~100)的给定点集,实验中选择点数为1000。分别用经典的Graham算法及本文算法对同一点集进行多次凸包运算,并比较它们的运算速度。使用Matlab6对实验结果进行绘图,如图5所示:

图5(a) 输入数据

图5(b) 凸包曲线

在程序中多次比较传统算法与改进算法的运行时间,结果如表1所示:

表1 传统算法与改进算法运行时间比较顶点数(1000)经典的Graham算法

450

图4 程序流程图

平均运算时间Pms

本文算法

100

(下转第43页)

第23卷第3期冷美萍等:基于马尔可夫随机场的医学图像分割

43

如图4(c)所示,改进的ICM算法分割结果如图4(d)所示。表1-1给出了用传统ICM算法和改进的

算法的参数比较。

进的算法大大缩短了运行时间,提高了效率。

表1 参数比较

两算法传统ICM算法

改进ICM算法

迭代次数106

计算时间全局收敛能量210s111s

113031121113823113

6 结束语

MRF具有完备的数学理论,包容性很强,内涵很广,有广阔的应用前景。根据医学CT图像的特点,建立了相应的基于MRF的图像分割模型,并将图像分割问题转化成图像标记问题,又进一步转化成求图像的MAP估计问题。本文讨论和实现了基

图4 结果比较图

于马尔可夫随机场的ICM算法对医学图像的分割,并改进此算法,对比分析了实验结果。

[参考文献]

从分割效果上看两种算法差异不大。但是改

[1] JameS.Duncan.NicholasAyache,MedicalImageAnalysis:ProgressoverDecadesandtheChallengesAhead[J].IEEETransaction

onpatteranalysisandmachineintelligence,2000,22(1):181-204.[2] 章毓晋.图像分割[M].北京:科学出版社,2001.

[3] 张鹏.Markov随机场在图像处理中应用的研究[D].武汉:华中科技大学,2005.

[4] 刘伟强.基于马尔可夫随机场的快速图象分割[J].中国图象图形学报,2001,6(3):228-233.[5] 胡阳涟.基于马尔可夫随机场的图象分割研究[D].西安:西安理工大学,2008.

(责任编辑 彭丹宇)

(上接第34页)

速度,算法时间复杂度小于O(nlogn)。在matlab环境中对大量随机产生的点集进行凸包实验,实验结果表明:与经典算法相比,本文算法效果非常明显,效率得到了很大的提高。

5 结束语

本文综合各种凸包求取算法,通过预先构造凸包边界,减少构建凸包的离散点数目,提高了运算

[参考文献]

[1] 刘广忠,黄琳娜.基于二叉树的算乱点集快速凸包算法[J],测绘科学,2008,33(4):86-88.

[2] 余翔宇,孙洪,余志雄.改进的二维点集凸包快速求取方法[J].武汉理工大学学报,2005,27(10):81-83.[3] 毛定山,崔先国,李行,等.简单多边形集凸包的快速算法[J].工程图学学报,2007(6):96-101.[4] 赵军,曲仕茹,等.平面点集凸壳的快速算法[J].计算机工程与应用,2009,45(1):56-58.

[5] 周文科.一种简单多边形凸包的快速算法及程序设计[J].广州大学学报:自然科学版,2003,2(6):545-547.[6] YaoAC.ALowerBoundtoFindingConvexHulls[J].JournaloftheACM,1981(28):780-787.[7] 郝晓军.凸包算法的加速与改进研究[D].天津:河北工业大学,2003.

(责任编辑 彭丹宇)

本文来源：https://www.bwwdw.com/article/1o01.html