边界为简单多边形的离散点Delaunay三角剖分及可视化研究.doc

边界为简单多边形的离散点Delaunay三角剖分及可视化研究边界为简单多边形的离散点Delaunay三角剖分及可视化研究刘立娜,徐云,贾进东,王鹏(信息工程大学测绘学院,河南郑州450052;沈阳军区65015部队,辽宁大连116023)【摘要】简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛地应用。本文提出了一种不需要判断多边形的凹凸性,直接对多边形建立最大凸包,在建立凸包的基础上建立Delaunay三角剖分的方法,设计了一个有效的数据结构。在剖分的基础上,去除三角形的内切圆圆心在多边形内的三角形即可得到满足需要的三角剖分。为了提高处理大规模数据的速度,实验中对数据进行了分块处理,提高了建网的速度。最后利用OpenGL技术实现了剖分后的地形三维显示。【关键词】简单多边形; Delaunay三角剖分;可视化【中图分类号】P28【文献标识码】A【文章编号】1009-2307 (2005) 03-0086-02收稿日期:2004-09-171引言多边形三角剖分是计算几何的一个几何基元。它可以简化问题规模,在计算机图形学、模式识别和GIS方面有重要应用。在3DGIS应用中,为了描述地形的起伏和表现真实的地表环境,需要对地形表面进行规则或不规则格网的划分。由于地形变化的不规律性和地形表面的不规则,在3DGIS中一般采用不规则格网划分,特别是三角剖分。然后利用对地面建立的三角网格数据,内插规则格网数据形成DEM(数字地面模型)从而实现地形表面的三维可视化。由于自然或人工地物轮廓形状的不规则性,三角剖分的实现具有很大难度。特别,当地形边界轮廓是凹多边形时,对其进行三角剖分就更加困难。为了解决对任意多边形的三角剖分,柳庆武等人提出了先判断凹凸性,然后在其基础上建立三角网的方法1;Cheng Siuwing等从建立最优三角形条件的角度提出了简单多边形三角剖分的算法;杨杰等提出了根据顶点凹凸性进行简单多边形三角剖分的算法,算法先定位凹多边形凹点,然后采用构造以凸点为顶点的三角形并层层剥去的方法3。以上算法基本上是在判断多边形凹凸性的基础上展开的。本文提供了一种对简单多边形的三角剖分方法,根据剖分结果实现了地形三维的可视化。2定义简单多边形(单域多边形):多边形的各边除顶点相交外都不相交。简单凸多边形:设简单多边形的给定顶点序列P1,P2,Pn按逆时针方向排列,并且点Pi+1在Pi-1Pi的左(右)侧,称由P1,P2,Pn构成的P(n)为简单凸多边形。简单凹多边形:设简单多边形的给定顶点序列P1,P2,Pn按逆时针方向排列,对点集P(n),如果点Pi+1在Pi-1Pi的左或右侧都有出现,称由P1,P2,Pn构成的P(n)为简单凹多边形。凸包:包含多边形的最大凸多边形3三角剖分原则边界多边形B(n)的三角剖分原则3:三角形与边界多边形B(n)不相交;三角形位于边界多边形内;边界多边形每相邻两节点属于同一个剖分;三角剖分满足Delaunay法则。4算法流程对数据整体进行自适应分块,决定分块个数及记录各块的基本信息。按照一定的规则,分别对每块建立初始凸包。图1流程图在每块中用逐点插入法进行构网,同时利用局部优化(LOP)动态修改与多边形某边相交的三角形。寻找每块的底线和顶线,将其合并,最终形成整体三角网。根据每个三角形的外接圆圆心,判断三角形是否在原有多边形的内部。是,则将其删除。否则继续,直到将所有的三角形搜索完毕。具体的流程图如图1所示。5具体的实现过程1)自适应分块由于实际地形的复杂性,离散点的分布很不均匀,若用同样大小的块,位于山区的块内点数会很大,而位于平坦地区的块内点数会很小,这些分块并不能提高建网的速度。为此,必须把块的大小设置成一个动态变化的值,我们以每块应包含的最少点数来表示。具体程序流程如下:于给定点集P,分别求出横、纵坐标的最大最小值。然后用点集内总点数除去每块的平均点数(预先给定),得到分块总个数,然后求出块宽度、块行数及块列数。由块行数、块列数和块宽度及起点坐标,就可求出各块的边界。检索整个点集P,将在此块边界范围内的点存入对应的点集中,若点数少于每块的最小点数(预先给定)转,第30卷第3期2005年6月测绘科学Science of Surveying and MappingVol30 No3Jun否则,继续下一块,直到所有的块都生成完毕为止。将该块(i, j)向正方向(i+1, j)和(i, j+1)扩展一个距离,修改该块中的数据,转。2)各块生成凸包Convex(D i j)求出块中所有点的min(x-y), min(x+y), max(x-y), max(x+y)。满足上述条件的四个点为初始凸包上的点。将凸包上的点以逆时针顺序组成一个链表,并通过一个递归过程Convex()来删除多余的点。对于每个凸包上的点I和其后继点J,反复调用递归过程Convex(),已确定在凸包线段IJ右侧的点。如果点在左侧,则将其前一点和后继点相连,去除掉该点,即该点是凹点。计算所有在IJ右侧的点到IJ的距离,求出距离最大的点K。将K插入到I, J之间,调用Convex(I, K)和Convex(K, J)。重复至,直到该块中无在凸包链表右侧的点为止。形成的凸包如图2所示。3)在每块中用逐点插入法进行构网构造凸包的Delaunay三角形是按照Delaunay准则,将凸包划分为Delaunay三角形。每生成一个三角形都用Delaunay准则进行测试,即三角形的外接圆不能包括凸包上的其他点。建立相关与每一个凸包点、凸包线、三角形的最初拓扑关系。对于非凸包上的点,插入时用最大、最小原则(Max-Min Angle Property)进行三角形局部优化(LOP)。在建立三角形时,根据数据结构中提供的变量判断其是否与多边形边界相交,如果相交则运用LOP优化。构成的Delaunay三角网如图3所示。局部优化(LOP):运用三角形的性质对由两个有公共边的三角形组成的四边形进行判断。如果其中一个三角形的外接圆包含第四个点,则将这个四边形的对角线进行交换。4)寻找两相邻子块的底线和顶线并合并设为HL, HR左右两个凸包,寻找过程可由连接HL最右点与HR最左点线段开始,对左右两块分别按顺时针、逆时针方向移动,直到所有点都满足在直线上侧(底线)或下侧(顶线)为止。两块的合并是一个迭代过程,它从连接HL, HR两块的底线开始,在两个子三角网TL, TR中寻找与底线组成Delaunay三角形的第三点L1, R1,选其中外接圆半径小的一个插入到最终的三角网中。新生成的连接左右两个子三角网的边成为新的底线,逐步上退至顶线结束。对于上下合并的子块也同理。5)剔除多余的多边形由于按照以上方法建立的Delaunay三角网是所有边界点形成的最大凸包的三角剖分,即在剖分的结果中包含了一些不在多边形之内的三角形,为了保证结果的正确性,必须将其剔除。读入包含边界线段的三角形;判断三角形的内切圆圆心在多边形内(利用VC中PtInRegion函数),是则删除该三角形。否,则继续,直到所有三角形检索完。6可视化与实验结果为了能够直观地显示所用算法构图的正确性,本文将实际的地形离散点数据作为实验,通过构建Delaunay三角网实现地形建模。为了实现三维可视化,本文将三角剖分后的地形内插成规则格网,利用格网点的z坐标表现地形起伏,实现三维效果显示。图4是三角剖分后的地形显示,图5是真实的三维显示。操作者可通过鼠标控制三维模型,从任意角度观察地形的三维形态。7结论本文主要研究了对边界为简单多边形的离散点数据的Delauny三角剖分,提出了一种不用判断多边形类型,而直接对多边形进行剖分的算法,最后借助于OpenGL三维环境,对构成的网格进行了光照渲染实现了地形三维可视化,验证了算法的正确性,也满足了视觉的需要。参考文献1柳庆武,等.凹多边形的矢量-三角形法自动识别与剖分J.计算机应用, 2003, 23(2): 77-79.21王鹏,刘立娜,等. GIS中Delaunay三角网的快速建立及拓扑自动生成J.测绘信息与工程, 2001(4): 24-27.3刘强.基于二叉树思想的任意多边形三角剖分递归算法J.武汉大学学报,信息科学版, 2002, 27(5): 528-533.4徐青,吴寿虎,朱述龙.近代摄影测量M.北京:解放军出版社, 2000.5柯正谊,何建邦,等.数字地面模型M.中国科学技术出版社, 1993.6武晓波,王世新,肖春生. Delaunay三角网的生成算法研究J.测绘学报, 1999, 28(1): 28-34.7王永明.地理信息系统方法M.北京:军事科学出版社, 1997.8王博等.一种加权剖分简单多边形为三角形和凸四边形子域的算法J.中国图像图形学报, 2002, 7(5): 486-490.9Lingas A. The Greedy and Delaunay Triangulations arenot Bad in the Average Case J. Information Process-ing Letters, 1986(22): 25-31.作者简介:刘立娜(1976-),女,汉族,吉林省榆树市人,硕士生,主要研究方向为数字城市、3DGIS。87第3期刘立娜武等边界为简单多边形的离散点Delaunay三角剖分及可视化研究image resolution merge、dynamic monitor、supervisedclassification etc, we quantificationally acquired the entironmentup-to-date state of Alxa league within 7 years. By validating132 outside samples, acquired dynamic monitor data andestablished understratum database of the entironment of Alxaleague. Supportted by the“sea quantity”GIS database, wecarried out quantitative dynamic analyzing of entironment of thewhole Alxa league. This paper introduces the quantitativedynamic analyzing result of the entironment of Alxa league.Key words:“3S”technicque; entironment; hungrinesssight; ejina oasis; haloxylon ammodendronWANG Cheng-an, AN Chun-mei, DU Bin,ZHANG Cheng-gong(Inner Mongolia Aerial Survey RmoteSense court,Inner Mongolia railway of telecast college,Inner Mongolia entironment surveillance station)Realization of basic geography spatial database on cyber-citybased on oracleAbstract:Basic Geography Spatial Database isfundamental platform for building cyber-city. Basic GeographySpatial data quantity is increasing by geometric series along withthe development of spatial surveying technology. It is animportant issue to organize, store and manager magnanimitybasic Geography Spatial data, so as to satisfy with nationaldigitalized product and development on national basic geographyinformation industry and promote preferably development ofcyber-city. The paper puts forward a method of realization onbasic geography spatial database with Oracle based on J2EE Tri-tier System framework.Key words:cyber-city; basic geography spatial database;GIS; J2EE; tri-tier system frameworkTIAN Mao-yi, LU Xiu-shan, ZHANG Yan, MAJin(Geoinformation Science & Engineering College,Shangdong University of Science and Technology, Qingdao266510, China;Department of Resource and civilengineering, Shangdong University of Science and Technology,Taian 271019;Chinese Academy of Surveying andMapping, Beijing 100039)A model of point cluster selection with circle charactersAbstract:This paper introduces a new method based ontransform of circle characters after analyzing current instances ofmap generalization. Five key steps of the algorithm aredescribed such as finding center point holding maximal emptyarea, calculating character space of map objects, transforminggauss coordinates to character space, line clustering in characterspace, and simplification line in character space. Finally anexample is given to show the efficiency of the method.Key words:map automatic generalization; selection;point cluster; circleQIAN Hai-zhong, WU Fang, DENG Hong-yan(Instituteof Surveying and Mapping, Information EngineeringUniversity, Zhengzhou, 450052, Henan)The delaunay triangulation and visualization of discrete pointsforming simple polygonAbstract:The Delaunay triangulation of Simple Polygon,being basic methods of calculate geometry, has been widelyapplied to computer graphics, 3D geographic modeling. Thispaper presents a method of establishing the biggest bulgy boxdirect from polygon without judging the polygons concavo-convex, and designs an efficient data structure. By this way,we can obtain perfect triangulation by eliminating thetriangulations that the centers of inscribed circles are within thepolygon. To quickly deal with data, we utilize the method ofdata block processing in experimentation. Finally, we realizethe 3D terrain representation using OpenGL.Key words:simple polygon; delaunay triangulation;visualizationLIU Li-na, XU Yun, JIA Jin-dong, WANG peng(Institute of Surveying and Mapping, Information EngineeringUniversity, Zhengzhou 450052, China)Tuning of database in system of spatial decision-making for e-governmentAbstract:The executing efficiency is very important forthe Oracle database application system as an extensive andcomplicated database. This paper discusses some tuning policieson database structure, SQL sentence and memory distributionof oracle9i database and brings foward some principles andmethods.Key words:Oracle9i; tuningLI Bin, ZHU Yi, SHI Li-hong, LIU Ji-ping(ChineseAcademy of Surveying and Mapping, Beijing, 100039,China)The design and application of oracle spatial databaseAbstract:By considering the trend of“Digital Earth”and“Digital Region”, Geographic Information System shouldprocess tremendous spatial data and its attribute data. Butnow, the individual storage of the data is not convenient fordata share and manipulation. Considering this, this paperintroduces the storage and management scheme of spatial data inOracle Database, brings forward a method for MapX to accessSpatial Database, and discusses the programming of spatialanalysis in the application system based on Oracle SpatialDatabase.Key words:oracle spatial; spatial data; mapX; spatialanalysisLIANG Hong, DING Ren-wei, ZHENG Hong-xia(Computer Science and Communication EngineeringInstitute