摘要
Delaunay三角剖分在计算几何、计算机图形学、计算机辅助设计、有限元分析、地理信息系统等邻域有广泛的应用,是一项极为基础且重要的离散数据网格化技术。生长算法是一种重要的Delaunay剖分算法,具有较高的理论价值和实际意义,该算法思路简单且容易扩展,可以拓展到三维点云曲面的构造中。但是现有的生长法效率不高,无法处理海量数据,本文经研究提出了一种基于Delaunay空圆性质的改进算法,在逐边定向扩展过程中直接利用Delaunay空圆性质,迅速缩小备选扩展点集的范围,大幅提高了三角网生长速度。大量的随机和规则数据测试表明该改进算法效率提升显著,与已有生长算法相比有10倍以上的提高,且数据量越大效率提升越明显。
Delaunay triangulation in computational geometry, computer graphics, computer-aided design, finite element analysis,geographic information systems and other neighbors have a wide range of applications, is an extremely basic and important discrete data gridding techniques. Growth algorithm is an important Delaunay triangulation algorithm, with high theoretical value and practical significance, the algorithm is simple and easy extension ideas, can be extended to construct a three- dimensional point cloud in surface. But the existing growth method is not efficient, can not handle huge amounts of data, this paper presents a study by an empty circle nature of inferences based on Delaunay improved algorithm by-side expansion process through verification extension points and extensions edge meets the Delaunay empty circle the nature of inference, you can quickly narrow the range of options for expansion point set, a substantial increase in the growth rate of triangulation. A lot of random and regular data tests show that the improved algorithm efficiency significantly, compared with the existing algorithms have grown more than10-fold increase, the greater the efficiency and the amount of data more obvious.
出处
《电脑知识与技术（过刊）》
2016年第8X期188-191,共4页
Computer Knowledge and Technology
