资源描述：
《基于ArcGIS环境下多类型数据的三角网和Voronoi图的生成》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、科技情报开发与经济SCI-TECHINFORMATIONDEVELOPMENT&ECONOMY2008年第18卷第4期文章编号:1005-6033(2008)04-0149-03收稿日期:2007-12-13基于ArcGIS环境下多类型数据的三角网和Voronoi图的生成12张勇,余斌(1.太原理工大学测绘科学与技术系,山西太原,030024;2.湖北省第一测绘院,湖北武汉,430074)摘要:基于渐次插入算法,在ArcGIS环境下,提取居民地中心点和道路中心线上的点作为离散点,实现了对这些离散点的Delaunay三角网的构建和数据的有效组织,利用
2、ArcGIS提供的接口生成了Voronoi图,实现了多类型数据Delaunay三角网和Voronoi图的生成。关键词:ArcGIS;Delaunay三角网;Voronoi图中图分类号:P208文献标识码:A多D-三角网的剖分算法都是根据Lawson所提出的这一思想演化而来1Delaunay和Voronoi图的定义及其优点的。根据三角网生成的步骤,可以将目前的三角网剖分算法分为三类[3]:一是分而治之算法;二是逐点插入算法;三是三角网生长算法。Delaunay三角网和Voronoi图是一组对偶图,将Voronoi图中各多边在Delaunay的生成算法
3、中,分而治之算法的优点是时间效率高,但形单元的内点连接后得到一个布满整个区域而又互不重叠的三角网结需要大量递归运算,因此占用内存空间较大;三角网生长算法的优点是构就是Delaunay三角网,而连接Delaunay三角网外界圆的圆心就得到占用内存空间较小,但时间效率较低,这两种方法是目前较常用的方法。Voronoi图。Delaunay三角网和Voronoi图是被普遍接受和采用的分析研逐点插入算法形象易懂,较易实现,逐点插入算法将未处理的点加到已究区域离散数据的有力工具,Delaunay具有3个特有的性质[1]:存在的Delaunay三角网中,每次插入
4、一个点,然后将Delaunay三角网重第一,外接圆规则:每个Delaunay三角形的外接圆不包含其他任何新定义。首先生成离散点的外凸多边形,然后内部用三角形分割之,判断离散点,也称之为Delaunay三角网的空外接圆性质,此特征已经作为创其余的点分别落在哪个三角形的外接圆内,以该点为顶点,把所在的三建Delaunay三角网的一项判别标准。角形一分为三,直到所有的点都插入为止,然后调用局部优化算法,把三第二,最小角最大性质:在由离散点集所能形成的三角网中,角网调到最佳。具体的步骤如下:Delaunay三角网中每个三角形的最小角度是最大的,这个性质也叫
5、做最(1)定义一个包含所有数据点并作为初始Delaunay三角形的超三小角最大规则。角形;第三,唯一性:由点集所形成的Delaunay三角网是唯一的,即无论使(2)从数据点中取出一点P加入到三角网中;用何种方法生成的Delaunay三角网都是一样的。(3)搜寻外界圆包含点P的三角形,将点P与此三角形三个顶点相Voronoi图又叫泰森多边形,泰森多边形的顶点是Delaunay三角网连,形成三个三角形;每个三角形的外接圆的圆心,它具有以下特性[2]:第一,每个泰森多边形(4)应用Lawson提出的局部优化法更新所有生成的三角形;内仅含一个离散点数据;第
6、二,泰森多边形内的点到相对应的离散点的(5)重复(2)～(4)直到所有点处理完毕;距离最小;第三,位于泰森多边形边上的点到其两边的离散点的距离相(6)删除所有包含一个或多个超三角形顶点的三角形。等。2.2Voronoi图生成算法Delaunay三角网和Voronoi图的优点是结构良好,数据结构简单,数Voronoi图可由连接相对应的Delaunay三角网的外心得到,本文采据冗余度小,存储效率高,与不规则的地面特征和谐一致,可以表示线性取三角网生长算法。在ArcGIS环境下,依据ArcGIS的数据结构,通过逐特征和叠加任意形状的区域边界,易于更新,可
7、适应各种分布密度的数点插入算法,实现了离散点的Delaunay三角网的构建,而Voronoi图则是据等;它的局限性是算法实现比较复杂和困难,但现在已经有了较多成利用ArcGIS提供的ITinEdit和ITinNodeCollection两个接口实现的。熟的实现算法。由于Delaunay三角网和Voronoi图本身的这些特点,决定了它在现3基于ArcObjects的Delaunay三角网的生成代地理科学和GIS空间分析中被广泛的采用,如GIS中的空间目标的综合、邻近性分析、影响区域分析、地表形态分析等都可以采用Delaunay三3.1基于ArcObj
8、ects的离散点和Delaunay三角网的数据结构组织角网或Voronoi图。目前,Delaunay三角网的生成算法和组织
