Nonconvex polygon identifier

Abstract

A method is provided for distinguishing nonconvex polygons from complex polygons. The present invention compares the edges of a polygon for self intersection points. Initially, "base" and "compare" edges are designated and bounding boxes for each of these edges are determined. The bounding boxes are then compared and if they intersect the edges may have points in common, whereas if no intersection occurs, then there are no common points and the edges are incremented and a comparison of other edges occurs. If it is determined that bounding boxes intersect, the intersection point for the edges under consideration is determined. If this intersection point lies within both bounding boxes, then the polygon is complex and the test ends. However, if the intersection point is outside either bounding box, then the edges are incremented and processing continues until all relevant edges have been considered.

Dependencies are inferred from the claim text.