基于四叉树结构的数字地表模型快速生成算法设计

摘要

为了研究数字地表模型的快速生成方法,在总结传统Delaunay三角化算法的基础上,给出了一个基于四叉树结构的数字地表模型快速生成算法的详细设计.该算法的基本思想是首先利用四叉树结构来对离散点进行分割,然后对四叉树叶节点进行Delaunay三角化,再两两合并四叉树节点三角网的凸壳,以快速生成地表格网模型.该算法是以四叉树为基本单位来实现限定边和限定多边形的快速嵌入;最后给出了算法在不同情况下的测试结果,并对测试结果进行了具体分析,给出了算法的时间效率分析和空间复杂性分析.实测数据结果表明,该算法有着较好的性能,而且也非常稳定.通过实测结果分析和算法的时间效率分析,可以得到算法的时间效率近似为O(nlog(n));通过算法的空间复杂性分析可以看出,算法可以自动适应不同的点空间分布情况,而且采用四叉树结构也非常有利于限定边和限定多边形的嵌入.