作者：靳海亮；李留磊；袁松鹤；耿文轩

第一作者单位：河南理工大学测绘与国土信息工程学院

摘要：针对传统三角网生长算法需要花费大量时间检索第三点的问题,对三角网生长算法进行改进,即对离散点集所在的区域由外到内进行矩形环式的分区,而后从内环到外环逐渐生成Delaunay三角形。每次查询第三点时,在当前环和其相邻的下一个环中进行,以减少第三点的查询范围并尽量保证第三点的正确查找。同时根据Delaunay三角形生成的顺序采取三角形基边先进先出的策略,保证当前矩形环状区域内的大部分点被加载至三角网中。在当前区域构网完成后,进入下一个相邻区域,如此循环构网,而后对三角网进行整体优化。采用C#语言进行算法的实现,结果表明,改进后的算法保证了构网的正确性、唯一性,也提高了构网的效率,对生产实践具有一定应用价值。

Abstract：In order to solve the problem of much time spent in searching for the third point, an algorithm of triangle network is improved to reduce the searching time. The algorithm is mainly focusing on dividing the area of discrete points into rectangular rings from the outside to the inside, and then forming the Delaunay triangle network from the inside rectangular ring to the outside rectangular ring. For each inquiry, the third point is searched from the current ring and the next ring to reduce the searching scope and ensure the searching accuracy. Meanwhile according to the Delaunay triangles forming sequence, the strategy of base-edge first-in-firstout is completed to ensure that most points in the current rectangular ring are included by the triangle network.When most of points in the current area are included by the triangle network, the next rectangular ring is set as the current area, then repeate the cycle and optimize the triangle network. The algorithm is realized in C#. The results show that the improved algorithm decreases the triangle network forming time and improves the accuracy which make it useful in the practices.

基金：国家自然科学基金资助项目(41541011)；

关键词：三角网生长算法;Delaunay;矩形环分区;

DOI：10.16186/j.cnki.1673-9787.2017.06.010

分类号：TP301.6