A general method for decomposing self-intersecting polygon to normal based on self-intersection points

Checking whether polygons are self-intersecting or not is an important step for GIS projects before they are published to the web. Automatically converting self-intersection polygons into normal ones is practically useful, especially there are numerous polygons need to be processed. Based on the relationships of self-intersection points, this paper presents an algorithm to convert a complex self-intersection polygon to a normal one which has no self-intersection part. Furthermore, using the relationships of the repeat points (original self-intersection points) of the decomposed polygon, the result of the only simple polygon can be split into independent sub-polygons bounded by those points. The algorithm is easy to understand and with high efficiency because we consider only the self-intersection point relationships of the polygon, and we do not pay attention to the edges and their directions. A point structure in which the relationships of the self-intersection points are defined is used in the algorithm.

Authors

• Yong Cui
• Qian Liu Sea AI Lab
• Guo Chen Nanjing University
• Hujun Zhang

Keywords

• Polygon
• Self-intersection
• Decomposing
• Splitting