摘要
分块式生成Delaunay三角网是加快构网速度的一个基本思路。已有的分治算法和其他分块合并算法能使平均时间复杂度接近线性,但算法复杂,编程难度大,且容易产生计算误差导致的错误。本文作者曾提出过一种基于三角网扩张法的逐块归并算法,它也是一种快速算法,但在算法中需要增加避免错误的判断规则,使程序变得较复杂。本文中的逐块生成法是对逐块归并法的改进,它继承了逐块归并法高效的优势,而且减少了判断规则,步骤更加简单。
Dividing the points into blocks and generating Delaunay triangulation from each block is the cardinal idea for fast crea- ting large Delaunay triangulation. Divide-and-Conquer algorithm and other divide-and-merge method at present have the time complexity of linearity but their steps are more complex and difficult to program, and it also raises the probability of occurring bugs from floatpoint errors. The author of this article proposed a sequential merging algorithm based on triangle-expanding method and it＇ s average time complexity is close to O（ n）, but in order to avoid float-point bugs, a judging rule must be added and thus the steps is some more complicated. The block-by-block generating method in this article is an improved modification of sequential merging method and inherits the high efficiency but more simple.
出处
《测绘科学》
CSCD
北大核心
2008年第6期133-135,共3页
Science of Surveying and Mapping
基金
国家自然科学基金项目(40572012)
