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

• 作者: 万洪涛 谢传节
• 来源期刊: 中国图象图形学报A辑
• 学科: 地球科学
• 关键词: 地理信息系统 数字地表模型 限定Delaunay 三角化
• 年，卷（期）: 2002,（4）
• 所属期刊栏目: 学术论文与技术报告
• 页码范围: 394-399
• 页数: 6页
• 分类号: P208
• 字数: 4835字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-8961.2002.04.016

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	万洪涛	中国科学院遥感应用研究所	10	621	9.0	10.0
2	谢传节	中科院地理科学与资源研究所资源与环境信息系统国家重点实验室	4	115	4.0	4.0