一种有效的无拓扑关系矢量多边形叠置算法

为了提高土地调查数据处理的效率，实现土地利用数据库中图斑的自动更新，本文提出一种有效的非拓扑关系矢量多边形叠置算法。本算法采用矩阵形式表达叠置多边形与底图多边形的空间关系，以减少参与叠置运算的数据量，构建每个底图多边形对应的叠置弧段链表，把复杂的多边形与多边形叠置过程转换为简单的线与多边形叠置，重新划分空间区域。通过实际应用表明，本算法能够计算出正确的叠置结果，避免了Weiler-Atherton算法中由于出入点配置出错引起的算法失败，具有较好的一般性。

An Efficient Algorithm for Vector Polygon Overlaying without Topological Relation

To improve efficiency of processing data in land survey and accomplish one - off alteration for all the polygons in database, an efficient algorithm for polygon overlaying is presented in this paper. Firstly, the matrix is constructed to express the spatial relationship between overlaying polygons and overlaid polygons, Meanwhile the quantity of the data to be processed is decreased. Secondly, the linestring list corresponding to each base polygon is constructed. Finally, the overlaying of polygon and polygon is transformed to the overlaying of line and polygon, and spatial area is repartitioned. Practical application confirms that the correct overlaying results can be obtained and the failure caused by the improper judgement of entry or exit points in Weiler - Atherton algorithm can be avoided efficiently. The algorithm has generality for most of polygon overlaying cases.