Construct bridges joining the holes the outer vertices

II.5 GENERIC CONVEX POLYGON SCAN CONVERSION AND CLIPPING

poly_scan and poly_clip. All fields of Poly_vert should be doubles. Note that incorrect settings of the interpolation mask can result in meaningless attribute values or wasted compute time. For C environ-ments that don’t have the bcopy routine, use #define bcopy (from, to,

GRAPHICS GEMS I Edited by ANDREW S. GLASSNER 86

II.6 CONCAVE POLYGON SCAN CONVERSION II.6

This program assumes the polygon is described by a single cyclic loop of points. To describe polygons with holes using this data structure, construct “bridges” joining the holes to the outer vertices. For example, if the outer polygon has vertices p[i] for 0 ≤i < np, and the inner polygon has vertices q[i]for 0 ≤i < nq, construct a single polygon consisting␣␣of␣␣the␣␣vertices:␣␣␣ p[0]...p[np␣– ␣1] ,␣␣p [0],␣q [0]...q[nq␣– ␣l] , q[0].The two new bridge edges connect vertices p[0] and q[0]in both directions.

Depending on the sorting algorithm used and the shape of the polygon, the complexity of this algorithm will be between O(n) and O(n2).