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

Vector Map Overlay Analysis Algorithm Based on Non-uniform Multi-level Grid Index

矢量地图叠加分析在实际场景使用中经常需要处理各种大规模复杂空间数据,因此算法整体分析效率的提升尤其重要。该文重点针对较大多边形对象和大量较小多边形对象的叠加分析使用场景,提出了一种有较强针对性的基于非均匀多级网格索引的矢量地图叠加分析(Non-uniform Multi-level Grid Index Overlay,NMGIO)算法,包括索引构建、网格过滤、叠加计算、拓扑构面4个步骤,通过对待分析数据集和叠加对象双向建立非均匀多级网格索引,利用数据的空间分布特点从根本上提升叠加分析效率。同时给出了算法整体时间复杂度和由C语言实现的原型系统叠加分析效果验证。

Vector map overlay analysis is often used to deal with large and complex spatial data in the actual scene, so it is particularly important of the study to enhance the overall overlay analysis efficiency. This paper focuses on the scene of large polygon object which overlays with a large number of smaller polygons and presents a strong targeted vector map overlay analysis algo- rithm based on non-uniform multi-level grid index （NMGIO）. This algorithm builds a two-way non-uniform multi-level grid in- dex of overlay analysis datasets and overlay object to use the spatial distribution of data to improve the efficiency of overlay analysis fundamentally. It can be broken down into four specific steps, including the index build, grid filters, overlay calculations and topological polygon build. And an overlay analysis of prototype system is implemented by C＋＋ language to prove the validation results as well as overall time complexity of this algorithm.