一种面向大规模空间数据的拓扑关系检查算法.pdf

第30卷第5期 地理与地理信息科学． V01．30No．5 2014年9月 and(洳rInfomationscience 2014 Geography September issn．1672—0504．2014．05．004 doi：10．39圈／j 一种面向大规模空间数据的拓扑关系检查算法 卢浩1，王少华1’孙，钟耳顺2，李绍俊1’2’3 摘要：空间数据拓扑关系检查是GIs应用中空间关系分析及网络分析的重要基础。该文主要面向通用性GIS平台 软件中的矢量数据拓扑关系检查，提出一种面向大规模空间数据的拓扑关系检查算法，介绍了算法设计思路、核心 数据结构、处理流程等内容，并针对使用较为频繁的“线内无重叠”、“线内无悬线”、“面内无缝隙”3个拓扑关系检查 规则进行了算法的详细阐述。最后，对这3个拓扑关系检查算法进行了对比验证和分析。实验表明，该算法在保 证拓扑关系检查结果正确性的基础上，具有较高的检查性能，适宜于大规模空间数据的拓扑关系检查。 关键词：大规模空间数据；拓扑关系检查；数据划分 中图分类号：P208 文献标识码：A 文章编号：1672一0504(2014)05一0017一05 研究发现：一方面，数据规模的高速膨胀对于拓扑关 0 引言 系检查的数据量提出了更高要求；另一方面，由于拓 随着GIS应用的深入，GIS平台软件所需支持 扑关系检查涉及的空间关系算子众多(目前主流 的数据量的规模也随之迅猛增长，空间数据库相关 理论和技术的发展为大规模空间数据的存储、更新、 算子)，在进行拓扑关系检查的总体设计和实施时， 读取等操作提供了较好的支持，因此对空间数据进 一种可支持拓扑关系多算子且面向大规模数据检查 行拓扑关系检查时，不可避免地涉及较大规模数据 的框架显得尤为重要。由于在进行拓扑关系检查 的检查操作。此时，支持大规模空间数据的高效拓 时，无论是单图层内的检查还是图层间的检查，拓扑 扑关系检查算法就显得尤为重要[1]，特别是在地籍关系的局部性特征使得面对大规模空间数据时进行 数据[2|、土地数据[3I、矢量地形数据[4|、管网排水模数据的合理有效划分成为可行的处理策略。 型[5|、数字线划地图[6]等应用领域。 1基于均匀格网索引数据划分的拓扑关系 目前学者对于空间数据质量的研究可分为以下 检查 方面：1)关于空间数据质量模型的研究[7]，主要面向 不同评价方法，提出相应的数据质量模型和数据质 在对各拓扑检查算子进行分析后发现，大多数 量度量模型。2)关于空间数据质量控制与评价技 的拓扑检查算子具有原子性和局部性特征。所谓原 术体系的研究[8舟]，主要面向数据生产过程，分析数子性是指虽然拓扑检查算子规则众多，但各规则都 据质量要素、建立数据质量模型、提出控制方法和评 可以拆分为节点间位置判定、节点与弧段间位置判 价体系。3)基于知识与规则的空间数据质量检查 定、弧段间位置判定和节点与多边形关系判定等基 研究∞’10|，针对空间数据质量问题本身的复杂性与 本原子操作，而复杂拓扑规则只是各种原子操作的 多样性，研究采用基于知识与规则的专家系统，将要 不同组合。另一方面，大多数检查算子都具有局部 素间的空间关系存放在规则库中，再将其与地物要 性的特征，即对图层中的对象进行检查时，对象间的 素进行比较、分析和判断，从而完成规则库对空间关 拓扑关系可分解为对象间局部节点与弧段的拓扑关 系的检查。总体看来，已有较多研究涉及模型定义 系组合。这一特征非常适合于采用均匀格网索引进 与评价体系的讨论，而对具体的检查算子实现方法 行空间数据划分，即均匀格网索引在显著降低空间 研究较少，本文则在已有研究基础上针