# 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 verticesq[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 verticesp[0] andq[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)andO(n2).