An Algorithm for Splitting Arbitrary Polygon
Liang Wu, Guang Tian, Zhong Xie · 2009
An algorithm for splitting arbitrary polygons with a polyline is described in this paper. Starting from introducing the existing theories in computational geometry and computer graphics, the paper describes the three major steps of this algorithm: 1) search lines with the sweep-line algorithm based on sorted edges of polygon, splitting polyline, and the most bounding rectangular determination; 2) calculate and select the intersection points, and save them in a node list together with the additional information needed in the last step of the algorithm; 3) construct the output polygons by performing independent walk-abouts through input polygons and the node list. This algorithm is able to do the common operations of arbitrary polygon splitting (convex and concave, curve edge, including finite number of holes). Also, it can split polygons with sharing edges. In the mean time, direct memory reading and overall computing strategy are adopted in implementation of the algorithm to enhance the efficiency.