改进的自连接Delaunay三角网生成算法  

AN IMPROVED ALGORITHM FOR AUTO CONNECTED DELAUNAY TRIANGULATION

作　　者：凌海滨[1] 吴兵[1] 

机构地区：[1]北京大学计算机科学技术研究所,北京100871

出　　处：《计算机应用》1999年第12期10-12,共3页journal of Computer Applications

基　　金：国家"九五"重中之重科技攻关项目!(96B020312)

摘　　要：本文提出了一个改进的自连接Ｄｅｌａｕｎａｙ 三角网生成算法。在原算法的基础上引进了封闭点的概念，在三角网的生成过程中动态地剔除封闭点，从而大大加快了生成新三角形时对点的查找过程。其次，通过对边扩展过程的研究，发现对除了第一个三角形以外的其他三角形实际上只有两条可扩展的边，新算法对这一点也进行了改进。最后，给出了实验的结果数据。In this paper, we presented an improved algorithm for auto connected Delaunay triangulation. Based on the original algorithm, we proposed the notion of closed point. During the process of triangulation, the closed points are dynamically removed, therefore evidently accelerates the process of searching new point while generating new triangle. Second, according to the observation on edge expanding during the algorithm, we found out that every triangle, except the first one, has actually only two edges that need to be expanded. We also applied this discovery to our algorithm. Last, the experimental result is given.

关 键 词：三角网 三角剖分 生成算法 地图制图 

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