作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2008, Vol. 34 ›› Issue (17): 254-256. doi: 10.3969/j.issn.1000-3428.2008.17.091

• 开发研究与设计技术 • 上一篇    下一篇

改进的Delaunay三角网渐次插入生成算法

许建中,马利庄   

  1. (上海交通大学电子信息与电气工程学院计算机科学系,上海 200240)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-09-05 发布日期:2008-09-05

Improved Gradual Imbedding Generation Algorithm for Delaunay Triangulated Network

XU Jian-zhong, MA Li-zhuang   

  1. (Computer Science Department, School of Electronic, Information and Electrical Engineering, Shanghai Jiaotong University, Shanghai 200240)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-09-05 Published:2008-09-05

摘要: 提出一种改进的Delaunay三角网渐次插入生成算法。在边界初始化阶段,无须对插入点进行排序,只须按链表顺序插入,在LOP算法中,因交换对角线而产生的新三角形只须遵循Delaunay三角化原则由里向外更新邻接三角形。实验结果表明,改进的算法能提高效率,加快Delaunay三角网的构建速度。

关键词: Delaunay三角化, 渐次插入, 局部优化过程算法

Abstract: This paper introduces an improved gradual imbedding generation algorithm for Delaunay triangulated network. The data points are inserted sequentially to construct Delaunay triangulated network without additional sorting operation. Based on the original insertion, the algorithm improves the efficiency of Local Optimization Procedure(LOP) algorithm by updating adjacent triangles, which uses Delaunay rules upon the triangles formed by changing diagonal lines. Experiment indicates that the algorithm can improve the efficiency of the former one and accelerate the generation of Delaunay triangulated network.

Key words: Delaunay triangulation, gradual imbedding, Local Optimization Procedure(LOP) algorithm

中图分类号: