分治法重建数字地形的子网凸包合并算法  

Subnet convex hull merging algorithm for reconstructing digital terrain models

作　　者：郑辑涛[1,2] 何红红[2] 张涛[2] 朱纪洪[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]北京航空气象研究所,北京100085

出　　处：《清华大学学报（自然科学版）》2015年第8期895-899,905,共6页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金资助项目(61104082)

摘　　要：该文深入研究了以往基于分治策略的数字地形重建方法,在实践基础上分析了参与合并的两个子网凸包的各种可能情况,针对传统合并算法的局限性和弊端,给出了一个子网凸包合并算法。该算法根据公共支撑线的性质,通过判断凸包顶点投影位置的关系确定公共支撑线和支撑点,然后在确保合理的前提下,在两个凸包之间交替生成新三角形完成两子网凸包的合并。实验结果表明:该算法稳定可靠,能够实现各种复杂情况下两子网凸包的成功合并。There are many digital terrain reconstructing methods based on divide and conquer.This study analyzes all possible cases of the merging of two subnet convex hulls.A subnet merging algorithm is then developed to overcome the limitations and drawbacks of traditional algorithms.The public support line and support points are found from the projection position of the vertices of the convex hulls.Then,the convex hull vertices between the support points are linked to generate new triangles so that no two triangles are intersect.Tests show that the algorithm is stable and reliable and that any two subnet convex hulls can be successfully merged.

关 键 词：子网 凸包 合并 数字地形 重建 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]