一种改进的Delaunay三角网生成算法  

AN IMPROVED GENERATION ALGORITHM OF Delaunay TRIANGULATION

作　　者：王强[1] 郑逢斌[1] 乔保军[1] 马庆华[1] 

机构地区：[1]河南大学数据与知识工程研究所,河南开封475000

出　　处：《计算机应用与软件》2010年第8期138-140,共3页Computer Applications and Software

基　　金：河南省科技厅重点科技攻关项目(0721022100)

摘　　要：Delaunay三角网在GIS/VR中用途广泛,分割—归并法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法。在研究基于这两种算法的合成算法后,对其进行了两点改进。一是简化凸壳的生成;二是三角形快速定位,通过确定向量之间的关系来解决点的定位问题,避免了复杂运算。实验结果证明,改进后的算法不仅继承原算法兼顾空间和时间的性能,且执行效率有明显提高。Delaunay triangulation has wide application in Geographic Information System and Virtual Reality, and its two prevalent genera- tion algorithms are the divide and conquer algorithm and the incremental insertion algorithm. After having studied on the compound algorithm based on them, two improvements were made against it. One was to simplify the construction of the convex hull, the other was the fast location of the triangle, by ascertaining the relationship among vectors to resolve point＇ s locating, thus the complicated algorithm was avoided. Experi- mental results showed that the improved algorithm succeeded to the performance of the original algorithm in giving consideration to both time and space, and its executing efficiency was enhanced remarkably.

关 键 词：DELAUNAY三角网 合成算法 三角形快速定位 凸壳 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]