Partition of a non-simple polygon into simple polygons.

摘要

While there are several algorithms to partition simple polygons into triangles, trapezoids, or monotone polygons, they do not handle self-intersecting (complex) polygons. In this work, we describe the theory, implementation, and testing of a new object-precision algorithm to partition a complex polygon into a set of simple polygons (possibly having holes) using the non-zero winding number rule to determine the “inside”ness of points in the polygon. The outline for the algorithm implemented and tested in this research was developed by Dr. Thomas Hain. This algorithm can be used as a preprocessing step to convert complex polygons into a set of simple polygons, which are then amenable to being processed by the algorithms mentioned above. We show that this algorithm yields better high resolution performance than the image-precision scan line algorithm [6]—the method currently used in practice.