基于QTM的球面Voronoi图生成算法与应用

王 磊

1. 河南理工大学测绘与国土信息工程学院，河南 焦作 454000； 2. 中国矿业大学(北京)地球科学与测绘工程学院，北京 100083

随着全球生态环境、社会经济一体化的不断深入，研究区域逐渐从局部区域扩大到整个地球，而摄影测量、遥感、全球定位系统等现代对地观测技术的快速发展，使得全球大范围、多尺度、多时相数据的获取成为可能。为了在全球范围内有效地管理和分析空间数据，需要构建一个全球的、连续的、多尺度的动态数据模型。球面Voronoi图(简称V图)，具有自然邻近、动态稳定等优良特性，已成为全球空间信息管理与分析最有潜力的解决方案之一。针对现有的球面V图生成算法在精度和效率方面存在的诸多问题，本文从球面V图的生成算法、动态维护及其应用方面进行了研究，主要内容如下：

(1) 提出了基于QTM的球面V图确定归属生成算法。本文将球面四元三角格网(quaternary triangular mesh, QTM)单元视作平面栅格算法中的像素(最小单元)，计算每个格网单元到所有种子点的距离，并通过比较得到最近的种子点作为相应QTM格网单元的归属，从而生成基于QTM的球面V图。试验结果表明，该算法能够将生成球面V图的误差控制在两个格网以内，初步解决了现有球面V图栅格生成算法的精度问题。

(2) 利用GPU对确定归属算法进行了优化(硬件优化)。确定归属算法具有计算密集性、指令一致性和相互独立性的特点，非常适合于GPU单指令多数据流的计算模型。本文采用GPU统一计算设备架构(CUDA)对算法进行实现，并从GPU全局内存、共享内存、常量内存、寄存器等内存的使用及访问方式等方面对确定归属算法进行了优化，以从整体上提高算法的效率。试验结果表明，利用GPU并行计算对算法进行优化后，效率可提高两个数量级以上。

(3) 利用双向扫描方法对确定归属算法进行改进(算法优化)。将球面按QTM的方式剖分后，依次按从左到右、从上到下和从右到左、从下到上的顺序对球面三角形单元进行扫描，并在扫描过程中通过计算和比较格网到其邻近格网的最近种子点的距离，得到当前格网的最近种子点，进而得到球面V图。试验结果表明，该改进算法大大减少了确定归属算法中不必要的计算，在同一层次下，球面V图生成时间基本恒定(与种子点数无关)。

(4) 利用QTM格网的层次性对确定归属算法进行改进(尺度优化)。首先利用低层次的格网生成球面V图，并根据QTM格网及其三邻近格网的归属信息提取构成Voronoi区域边界的QTM格网；然后对边界格网进行再次剖分，利用确定归属算法确定边界格网子格网的归属，以此得到更高层次的球面V图，重复该步骤直至达到相应层次。试验结果表明，算法效率相对于确定归属算法有较大提高，且能够生成更高层次的球面V图。

(5) 试验系统设计开发与应用。设计开发了基于QTM的球面Voronoi图算法与应用试验系统，利用不同类型的数据，从效率、精度等方面对各算法进行了验证；同时，还给出了球面Voronoi图的动态维护操作方法和基于栅格Voronoi图的球面自然邻近插值方法，并对基于质心Voronoi图的全球地形自适应建模方法进行了初步的探索与试验。