基于非均匀多级网格索引的矢量地图叠加分析算法

0　引言

随着空间分析技术的发展，GIS将从一般的空间事务处理转向空间决策支持[1]，且已从数据库型GIS进入分析型 GIS的阶段[2]。矢量地图叠加分析算法是 GIS分析中的重点和难点，叠加过程被认为是 GIS发展过程中最具挑战性的问题之一;而叠加分析过程中的退化情形以及浮点计算的有限精度使得矢量数据叠加计算更加困难。因此，从学科的角度看，地图叠加分析算法是地理信息科学的重点与难点[3]。同时，随着 GIS应用的不断深入，面向大规模复杂数据的叠加分析性能的要求也逐步提升。

叠加分析按照几何运算方式分为裁剪、擦除、同一、相交、对称差、合并、更新等，其操作对象主要是点、线、面数据，同时栅格数据也有类似的叠加分析方法。现有叠加分析方法多使用空间索引(将整个空间划分成不同的搜索区域，以一定的顺序在这些区域中查找空间实体[4])的方法来实现，这是由于使用空间索引可提高对空间数据获取的效率[5]。当前空间索引研究集中在空间索引和存储结构的结合、索引效率与检索效率的平衡以及面向移动目标的存储和索引等方向[6]。目前主要的基于多边形裁剪的叠加分析算法包括 Weiler-Athernton算法[7]、Vatti算法[8]及 Greiner-Hormann算法[9]，刘勇奎等[10]给出了基于单向链表结构的一般多边形的裁剪算法。

在 GIS实际应用中，广义叠加分析主要包括栅格图层间的叠加操作与矢量图层间的叠加操作。栅格叠加是逐个在每个地图像素或网格单元上进行布尔算术操作，比矢量叠加相对容易实现[11]。矢量地图根据数据类型不同，又可以细分为点面叠加、线面叠加和面面叠加，其中应用范围最广、功能实现难度最大的是面面叠加操作，其主要挑战包括矢量数据误差导致的叠加结果准确性和大规模复杂空间数据下的分析性能，而本文主要针对在 GIS应用中常遇到的较大对象对于大量较小对象数据集的叠加分析。

更多内容请查看pdf