基于海量数据delaunay三角网构建研究与实现

《基于海量数据delaunay三角网构建研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：P22密级：公开UDC：单位代码：10424学位论文基于海量数据Delaunay三角网构建研究与实现王星申请学位级别：硕士学位专业名称：数字矿山与资源勘探指导教师姓名：卢秀山职称：教授山东科技大学二〇一二年五月论文题目：基于海量数据Delaunay三角网构建研究与实现作者姓名：王星入学时间：2009年9月专业名称：数字矿山与资源勘探研究方向：“3S”技术集成与应用指导教师：卢秀山职称：教授论文提交日期：2012年5月论文答辩日期：2012年6月10日授予学位日期：ConstructionAndAchievementOfTheD

2、elaunayTriangulationBasedOnHugeAmountsOfDataADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFENGINEERINGFromShandongUniversityofScienceandTechnologybyWangXingSupervisor:ProfessorLuXiushanGeomaticsCollegeMay2012山东科技大学硕士学位论文声明本人呈交给山东科技大学的这篇硕士学位论文，除

3、了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名：日期AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknowledge.Thedo

4、cumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Date:山东科技大学硕士学位论文摘要摘要海量数据的Delaunay三角剖分在“数字城市”、“数字矿山”等GIS三维建模领域具有重要的意义。本文主要研究海量数据Delaunay三角剖分的算法实现。本文以传统的Delaunay三角剖分算法为研究对象，分析对比三角网生长法、逐点插入法及分治法各自的优缺点。通过分析传统的Delaunay三角剖分算法，结合目前海量数据Delaunay三角

5、剖分的特点，提出一种基于格网分割的Delaunay三角剖分算法。在基于格网分割的Delaunay三角剖分算法中，首先将海量数据分割为大小相等的若干块子数据，然后对分割后的子数据块进行Delaunay三角剖分，最后将所有的子块剖分数据进行合并，实现海量数据的三角剖分。在子块数据的Delaunay三角剖分的过程中，本文利用逐点插入法生成Delaunay三角网。首先，利用凸包算法计算子块点数据的凸包，然后利用逐点插入法将除凸包点外的所有点插入到子块中，同时生成及不断优化三角网。在向凸包中插入未知点时，如果利用直接计算插入点的影响三角形区域的

6、方法进行三角网优化时，则可能出现不连贯的影响区域的问题，影响三角形的正常生成。为此，笔者先寻找插入点所在目标三角形，然后查找目标三角形的边，最后查找与边有关的三角形是否为插入点的影响范围。利用此方法可以解决并优化三角形影像区域不连贯的问题。在格网间三角网合并过程中，首先分析不同格网间所有凸包连接过程中可能出现的多边形形式（凹多边形，凸多边形），然后根据多边形类型分别进行三角剖分，从而达到格网间多边形合并的目的。在此过程中，凹多边形主要分为两种形式：简单凹多边形与自相交凹多边形。在自交凹多边形剖分过程中，首先要解决其自相交的特性，将自相

7、交凹多边形转化成简单多边形，然后利用简单凹多边形剖分的方法，进行凹多边形剖分，实现格网间三角网的合并。另外，本文还研究了java3D可视化技术，总体把握了java3D技术可视化的原理与方法。在海量数据Delaunay三角网剖分系统实现时，利用java3D的可视化技术实现三角网的三维可视化。在系统中还实现了三维漫游、定点查询、测距查询，三维坐标查询等实用功能。关键词：海量数据；Delaunay-TIN；三角形剖分；DEM山东科技大学硕士学位论文摘要ABSTRACTDelaunaytriangulationabouthugeamounts

8、datahasgreatsignificanceintheGISthree-dimensionalmodeling,suchas“DigitalCity”,“digitalminefield”.Thispaperrese