简单矢量数据多边形裁剪问题的图模型

Graph Model of Polygon Clipping Using Simple Vector Data

无拓扑信息的矢量数据多边形裁剪问题是解决GIS叠置分析的基础。本文借鉴GIS中弧段结点模型的思想,建立描述两多边形集合间裁剪问题的图模型,以解决现有算法实现在处理大数据量裁剪时暴露的问题。模型运用图中定义的顶点和边分别表示结点和弧段,使集合间实体的关联性得以增强,结果区域边界的重组过程得到简化。针对海量数据的存取特性,设计并实现该模型的数据组织方式及其构建算法。最后以大数据量GIS叠置分析为例,将本文实现与Vatti算法实现加以比较,实验表明,本实现在进行大数据量的两多边形集合裁剪时效率较高,同时,程序具有合理调配其内存空间中栈和堆资源使用的能力,这使其健壮性强于后者。

The basis of overlay analysis in GIS is to solve the problem of polygon clipping by using vector data without topological information.The defects of current clipping algorithms used to process large data are analyzed in this paper.Based on the idea of arc-node model in GIS,a new graph model is established to describe the clipping issues between two polygon sets.The node and arc are represented respectively by the vertex and edge defined in the graph model,which strengthens the relevance of polygon sets and ...