摘要
提出了一种基于改进的Graham扫描法的分块构建不规则三角网算法。采用分割合并的思想,先对平面上的离散点集区域进行分块,然后对各个子块用改进的Graham扫描法生成不规则三角网,再从边界边出发依次合并相邻的三角网子集,直到所有子集合并结束。本算法采用分块的思想缩小了构网时的搜索范围,对子块用改进的Graham法生成三角网提高了算法性能。实验结果表明,本算法使构网效率有很大的提高。
An algorithm of constructing Delaunay triangulation based on the improved Graham' scan was presented in the paper.The algorithm firstly splits the discrete point sets into several subsets by mesh partition,then it builds triangulated irregular networks on these subsets,finally it merges these triangular networks one by one sequentially.The splitting method of this algorithm can decrease the search scope of points remarkably.The use of improved Graham' scan to build Delaunay triangulation of sub-block increases the performance of the algorithm.The result of our experiments shows that the algorithm has a distinct superiority in the efficiency of constructing irregular network.
出处
《江南大学学报(自然科学版)》
CAS
2010年第2期191-195,共5页
Joural of Jiangnan University (Natural Science Edition)