改进Delaunay生长算法研究  

Improved Delaunay giftwrapping algorithms

作　　者：张渭军[1] 

机构地区：[1]长安大学地球科学与资源学院,西安710054

出　　处：《测绘科学》2011年第4期58-59,共2页Science of Surveying and Mapping

基　　金：国家自然科学基金资助项目:(40472131);中央高校基本科研业务费专项基金资助(CHD2009JC161);长安大学基础研究支持计划专项基金资助

摘　　要：本文在Delaunay-三角网的特性及其生成算法基础上,针对分割-归并算法、逐点插入法的局限性,在生长算法的基础上提出一种改进生长算法,随着Delaunay-三角网生成过程,该算法通过设置动态点链表,使点链表中的可用点逐渐减少从而节省时间,其次针对原算法中三角形有两种可扩展边的可能,每次都取边表中最后压入的边为基边来生长,这样每次生长都从每一个三角形的第三条边进行生长,这样才能保证三角形生长的正确性;试验结果表明该改进生长算法相对于传统生长算法在一定程度地节省了构网的运行时间。To efficiently establish Delaunay-triangulation, the paper introduced its properties and classification algorithm and presented an improved algorithm on the base of giftwrapping algorithms for the limitation of divide-conquer and incremental algorithms. With the generative process of Delaunay, the improved algorithm instituted dynamic point-list and made the usable points decreasing and saved the time. Second, finding the last pressed edge from the edge-list and making it gifiwrapping edge, the improved algorithm made the triangle giftwrapping from the third edge against the other two possible edges. The result proved the improved that the giftwrapping algorithm was feasible.

关 键 词：Delaunay-三角网 分割一归并算法 逐点插入法 生长算法 点链表 

分 类 号：P282[天文地球—地图制图学与地理信息工程]