An intersection points determining algorithm for polygon overlay operation

This paper describes an algorithm for determining intersection points of polygons. Additional information of intersection points is stored in an oriented single list which is used for the constructing of output polygons in overlay operation. Overlay operation is one of the most important functions in GIS spatial analysis. In GIS application, polygons are usually complex (convex or concave, with or without holes) with huge number of vertices, and also, there are two or more map layers for overlay. Therefore, this algorithm adopts overall computing strategy, picks up all edges of input polygons and sort them in one direction (overlapping edges are selected), and then determines intersecting and touching edges by sweep-line and rectangle test. In order to avoid repeating intersection points calculation, touching edges are polylinized and considered as line segments for further computing. Overall computing strategy and non-repeating intersection points are efficiently adopted in GIS overlay operation.