摘要
在对传统构建Delaunay三角剖分 (尤其是分割 合并 )算法进行分析的基础上 ,采用自适应格网划分方法对点集进行排序、分割 ,并按照逆序合并Delaunay子三角网 ,然后进行约束处理 ,快速、高效地实现了Delaunay三角网的构建 ;对Delaunay子三角网合并、地性线处理、平三角形处理等关键问题进行了描述。实测结果表明 ,该算法的时间复杂度接近于O(n)。
Based on the analysis of common Delaunay triangulations methods,especially the divide-and-conquer method,a faster algorithm for constructing Delaunay triangulations is presented.It divides the point set by self-adaptive grid,constructs and merges the sub-triangulations.The key problems of merging sub-triangulations,dealing with the terrain features and the flat triangles are described.The experiments show that the expected time of the algorithm is O(n).
出处
《北京大学学报(自然科学版)》
CAS
CSCD
北大核心
2003年第5期736-741,共6页
Acta Scientiarum Naturalium Universitatis Pekinensis
基金
国家"十五"86 3高技术规划专题 (2 0 0 1AA135 180 )
教育部重点 (990 0 3)资助项目