基于简单要素模型的多边形分割算法

Algorithm for Splitting Polygon Based on Simple Data Model

多边形是GIS研究和应用中使用最频繁的几何对象,该文描述了基于简单要素模型的任意多边形分割算法。从计算几何出发,结合GIS空间数据的特点,将基于简单要素模型的多边形分割算法设计为:1)对多边形及分割线的边界排序,基于扫描线及外包矩形检测查找可能相交的线段,提高相交线段的搜索效率;2)计算交点生成结点信息(包括交点坐标、线号及交点的出入),并存储在独立的单向链表中;3)根据结点链表和原多边形坐标搜索结果多边形。该算法能够分割任意简单多边形(凹凸、曲线边界和带洞的多边形)以及有共享边的多边形。最后在MapGIS7.0平台上,实现了基于简单要素类的多边形分割功能。

The polygon is the most frequently used geometric object in GIS research applications, in this paper, an algorithm for splitting arbitrary polygon based on simple data mode is described. The algorithms of polygon unions and intersections, erasing, clipping are discussed and analyzed. Based on the study of the domestic and foreign literatures, considering the feature of spatial data, this algorithm for splitting a polygon with a polyline is completed. It works in the following steps. First, to inspect and prepare spatial data based on simple data mode. The polygons being split must be well-defined polygons. Then, to find intersection lines with sweep-line algorithm based on sorted lines which are the edges of polygons and splitting polyline. Bounding rectangular test is used first in this step. And then, to calculate the intersection points, and construct node lists of intersection points and other additional information（coordinates of intersection points, line number, from-to and so on）. The start point of polygon is considered as intersection point. Last but not least,the output polygons are constructed by performing independent walk-about through the node lists. The theoretical time complexity is O（v＋a） log2 （v＋a）（v and a are the number of the polygons＇ and polyline＇ vertices）. This algorithm can calculate arbitrary polygons which are well-defined polygons, including shared edges. Tested in MapGIS7. 0 platform, the splitting polygon algorithm based on the simple data has been realized.