摘要
提出了一种快速Delaunay三角网生成算法。算法采用分割合并的思想,首先对离散点按一定的阈值进行二叉树的分割,对每个叶子节点分别构建三角网,再从底向上进行合并具有相同父节点的块,在合并的过程中同时进行LOP优化,生成Delaunay三角网。在使用逐点插入法子块构网过程中,提出了一种三角形快速定位方法。最后通过和其他算法实验数据的比较,表明采用二叉树分块构建Delaunay三角网具有较好的效率。
An algorithm for quick generating of Delaunay triangular net is proposed in the paper. The thinking of division-mergence is adopted in the algorithm-forming. At first, the discrete points are divided according to the binary tree method with a certain threshold value; secondly, the triangular net is constructed for each leaf sub-node; then,the blocks with same parent node are merged from bottom to top and the optimization of the triangular net is conducted in the process with LOP algorithm. In the process of sub-block generation of the triangular net with the insert method point by point, a method of quick triangular positioning is proposed. At last, through the comparisons with other algorithms, the algorithm for generating Delaunay triangular net based on blocks of binary tree has a higher efficiency.
出处
《山东科技大学学报（自然科学版）》
CAS
2009年第2期97-101,共5页
Journal of Shandong University of Science and Technology(Natural Science)
基金
矿山灾害预防控制教育部重点实验室开放基金项目(MDPC0808)
