一种基于格网划分的高效Delaunay三角网格化算法  

An Efficient Delaunay Triangulation Algorithm Basing on Grid Partitioning Approach

作　　者：曾闽山[1] 田冬玲[1] 郭吉民 

机构地区：[1]中国矿业大学资源与地球科学系 [2]中国石油华北油田分公司采研院

出　　处：《微计算机信息》2006年第03X期127-130,共4页Control & Automation

基　　金：高等学校博士点基金20050290009

摘　　要：对于任意给定的平面散点数据,可以通过Delaunay三角剖分进行网格化处理。但是当数据量较大时,一般的Delaunay三角网格化算法建模过程非常复杂,且内存消耗大,执行效率低。本文在传统的分割-合并算法基础上,对已经进行块分割的格网数据进行排序、再分割,然后按照分割的逆序合并Delaunay子三角网,高效快速地生成Delaunay三角网格,有效地提高了建模效率,其时间复杂度接近于Ο(n)。An efficient Delaunay triangulation algorithm is introduced to create triangulation irregular networks for massive iregular 2D datum in this paper. Based on the traditional divide-and-conqu- er algorithm and grid partitioning approach, tiny and selfadaptive datum blocks divided and sorted iteratively, are created and merg- ed reversely, while Delaunay triangulation network is generated efficiently at the same time. Finally, the datum experiments show that the self-adaptive divide-and-conquer algorithm basing on grid partitioning approach has more efficiency, and its time complexiW approaches to O（n） .

关 键 词：格网 DELAUNAY三角网 分割-合并算法 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]