关键词:二叉树; Delaunay三角网; Graham扫描技术; 数据分块
Efficient algorithm of constructing Delaunay triangulation based on
binary tree and Graham scanning technique
LI Gen, ZOU Zhi-wen,JU Shi-guang
(College of Computer, Jiangsu University, Zhenjiang Jiangsu 212013, China)
Abstract:In order to enhance the speed of constructing triangulated irregular network, this paper proposed an efficient algorithm of constructing Delaunay triangulation. Firstly, split the set of discrete points into several subsets with a threshold value and built an index binary tree during that process. Secondly it built Delaunay triangulation on these subsets by Graham scanning technique. Finally, merged the blocks with the same parent node from bottom to top. The result of the experiments shows that the algorithm, compared with other ways, has a distinct superiority in the speed of constructing irregular network. ......