An algorithm of Delaunay triangulation network growth based on rectangular ring partitioning
JIN Hailiang
LI Liulei
YUAN Songhe
GENG Wenxuan
Abstract：In order to solve the problem of much time spent in searching for the third point,an algorithm of tri-angle 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 accu-racy. Meanwhile according to the Delaunay triangles forming sequence,the strategy of base-edge first-in-first-out 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.
Keywords：triangle network growth algorithmDelaunayrectangular ring partitioning
Publication Date：2017-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：6( 63-68 )