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

作     者：谢传节 万洪涛 

作者机构：中科院地理科学与资源研究所资源与环境信息系统国家重点实验室北京100101 中国科学院遥感应用研究所北京100101 

基　　金：国家自然科学基金项目 (4 93 710 5 1) 

出 版 物：《中国图象图形学报（A辑）》 (Journal of Image and Graphics)

年 卷 期：2002年第7卷第4期

页      码：394-399页

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

主 题 词：地理信息系统 数字地表模型 限定Delaunay三角化 四叉树结构 快速生成算法 GIS 

学科分类：081603[081603] 081802[081802] 07[理学] 08[工学] 070503[070503] 0818[工学-交通运输类] 0705[理学-地理科学类] 0816[工学-纺织类] 

核心收录：

D　O　I：10.11834/jig.200204130

馆 藏 号：203373627...