METHOD FOR POLYGON DECOMPOSITION

A method for decomposing a polygon into trapezoids and further decomposing the trapezoids. During the decomposition process, the method classifies vertices having a horizontal edge by traversing the active trapezoid list, and using the trapezoids found in the list to aid in classifying the vertex. When a polygon fully contains another polygon, the method slits a diagonal between the outside polygon and the inside polygon to create a single polygon. During the slitting produces, vertices are duplicated and diagonals connecting to the original vertex are left connected to the original vertex or are connected to the duplicated vertex. The method corrects improper ordering of the inside polygon, and the method provides consistency checks during the decomposition process to detect polygons with intersecting edges.