Electronic Arts Inc.
Computer Handling of Polygons

Abstract:

A computer implemented method of handling polygons is disclosed, including polygons which are complex and include degeneracies. The method includes receiving an input polygon with at least one boundary, the at least one boundary having at least one vertex joining edges of the polygon boundary; determining an edge direction for each of the edges; determining a signed exterior or interior angle of each vertex angle wherein, if the exterior angle between the edges is pi or pi to within a predetermined threshold, determining the signed angle of the vertex angle including assigning a sign based on the winding of the edges of the polygon boundary, a sequence of angles of polygon vertices which can be directly computed or retrieved from a memory, the geometrical property that all exterior angles of the polygon sum to -2 pi or 2 pi, and the known sign of the polygon area.