摘要
Delaunay三角网在很多领域都有着广泛的应用,快速高效地生成Delaunay三角网十分重要。逐点插入法是构建Delaunay三角网中使用最广泛的方法之一。本文深入研究了使用逐点插入法构建不带约束条件Delaunay三角网的过程。在使用该方法生成Delaunay三角网中建立结点拓扑关系这一影响构网效率的关键步骤中引入了Qi算法,简化了该方法生成Delaunay三角网的复杂度。然后在向Delaunay三角网内插入约束边的过程中,再次引入Qi算法,从而提高了构网的效率。为了验证上述模型,我们在Microsoft Visual Studio 2005开发环境下,以C#为开发工具,采用底层开发模式实现了改进的逐点插入法,实验证明引入Qi算法能够提高逐点插入法Delaunay三角网构建及插入约束边的效率。
Delaunay Triangulation has a wide range of application in various fields,and it is very important to generate Delaunay Triangulation efficiently.After analyzing the procedure of construction of Delaunay Triangulation without control boundary using point-insertion method,the authors introduced the Qi algorithm to the key step of building node-topology.The Qi algorithm was adopted again when inserting constrained boundaries into the Delaunay Triangulation to improve the efficiency.In order to verify the algorithm presented in this paper,the authors implemented algorithms using C in VS.NET.The experiment shows that the introduction of the Qi algorithm can improve the efficiency of building Delaunay Triangulation using point-insertion method.
出处
《遥感信息》
CSCD
2011年第1期92-96,共5页
Remote Sensing Information
基金
"十一五"国家科技支撑计划项目2006BAJ09B02