一种改进的用于三维DT剖分的三角网生长算法  

An improved triangulation growth algorithm for 3D delaunay triangulation

作　　者：许克平[1,2] 

机构地区：[1]福州大学福建省空间信息工程研究中心,福建福州350002 [2]空间数据挖掘与信息共享教育部重点实验室,福建福州350002

出　　处：《微型机与应用》2014年第15期65-68,共4页Microcomputer & Its Applications

基　　金：国家高技术研究发展计划(863计划)课题(012SS012AA102002)

摘　　要：三角网生长法具有独特的优势,但将其扩展到三维的研究远远少于逐点插入法、分治法以及二者的合成算法,研究扩展三角网生长法实现三维DT剖分的算法。引入k近邻思想优化了原始算法,时间复杂度可达O(NlogN),且改进对二维、三维算法都有效。通过AE二次开发完成了数据操作、算法实现和二维、三维显示等功能,后续能够较方便地添加和扩展ArcGIS相关功能以及其他数据挖掘算法模块。用两组6个点集数据进行实验分析,网格构建时间对比验证了算法性能。Triangulation growth algorithm has its unique advantages, but researches about developing it into an 3d algorithm are much more less than the ones about developing incremental insertion algorithm, divide ＆amp; conquer algorithm and their compound algorithm. This paper studies the algorithm for 3d delaunay triangulation by developing triangulation growth algorithm, optimizes the original algorithm with k-nearest neighbors thought so that algorithm time complexity becomes O （ NlogN ） , the optimization is valid both for 2d and 3d algorithm. Uses ArcGIS Engine secondary development program to achieve data manipulation, algorithm implementation, and display of two three-dimensional mesh graph, some ArcGIS related functions and other data mining algorithms modules can be easily added to the program. Taking six sets of point data as example for experimental analysis, grid construct time comparison verifies the ability of the algorithm.

关 键 词：三维 DT 剖分 三角网生长法 k 近邻思想 

分 类 号：P208[天文地球—地图制图学与地理信息工程]