Generalized-Trapezoidal Decomposition Algorithm for Planar Polygons

To meet the demand for decomposing geometric shapes by machinery embroidery and pocket machining, we put forward a definition of generalized-trapezoid and a generalized-trapezoidal decomposition algorithm. The definition of generalized-trapezoid is by integrating the trapezoid with monotone chain, and the generalized-trapezoidal decomposition algorithm is based on vertex classification and a scan line approach. It borrowed ideas from the frame of fast trapezoidation technique presented by reference (Lorenzetto G P, Datta A, Thomas R C. A fast trapezoidation technique for planar polygons. Computers & Graphics, 2002, 26(2): 281～289). The algorithm can decompose a complex planar polygon with nesting holes, and its time complexity is O(nlogn) by analysis and testing.