黄 艳，卢学良

1.西安测绘研究所，陕西 西安，710054;

2.地理信息工程国家重点实验室，陕西 西安，710054

1 引 言

数字高程模型(digital elevation model，DEM)作为一种表达地形的数学模型，自1958年由美国麻省理工学院Miller教授提出以来，由于其表达方式直观多样、便于更新等优势，已经在测绘导航、农林规划、地学分析等领域得到了广泛的应用和研究，成为国家经济建设以及国防建设的重要基础数据之一[1]。DEM的生产途径多种多样，目前应用最为广泛、生产效率最高的方法一般是通过航空航天摄影测量、合成孔径雷达干涉测量或是机载激光扫描等方式获取地形地物的点云数据，然后通过内插的方式获得规则格网的DEM[2，3]。在这些方法中，插值是DEM生产的重要环节，常用的DEM插值算法有反距离加权插值算法、谢别德插值算法和径向基函数插值算法等[4，5]，这些算法无不是利用待插值点邻域范围内的已知采样点通过特定的加权方式完成插值。因此，邻域采样点的获取是完成插值的前提，而为了高效获取待插值点的邻域采样点，一般要对点云建立空间索引，常用的空间索引方法为栅格法。本文在深入分析栅格法索引的基础上，引入了KD树来实现邻域点的快速获取，并通过试验对两种空间索引的效果进行了对比分析。

2 DEM插值

DEM插值是根据已知采样点的高程值去估计未知插值点高程值的过程[6]，其主要用于缺值估计、等值线内插和离散点云数据的格网化[7]。DEM插值可以通过已知采样点来估计未知插值点，主要是因为地形具有空间异质性和空间相关性等基本特征，使得利用一些空间位置合理的采样点(一般为邻域采样点)获得对地形表面相对精确的描述成为可能。……