🚀 go-pugleaf

Timothy Beres (tim@tslvax.uucp) asks how to decompose a concave polygon
into triangles and trapezoids with horizontal top and bottom.
I think the best approach would be a scan conversion algorithm.
Below is the outline of a simple scan converter for concave polygons which
has worked well for me; it could easily be modified to output trapezoids
and triangles.

To scan convert polygon having n vertices X[i] Y[i]:

create y-sorted array of indices ind[k] into vertex list: Y[ind[k-1]]<Y[ind[k]]
for (k=0, y=ymin; y<=ymax; y++) {
    /* maintain list of currently active polygon edges crossing scan line y */
    for (; k<n && Y[ind[k]]<=y; k++) {
	i = ind[k]
	/* invariant: y-1 < Y[i] <= y */
	insert or delete edges before and after vertex i (i-1 to i and i to i+1)
	    from active list if they cross scan line y
    }
    sort list of m active polygon edges by x of intersection point with line y
    for (j=0; j<m; j+=2) {
	/* span between j and j+1 is inside, span from j+1 and j+2 is outside */
	draw pixels between active[j].x and active[j+1].x
    }
}

This scan conversion algorithm requires no special cases for horizontal edges
as many others do.
-- 
Paul Heckbert
Pixar				415-499-3600
P.O. Box 13719			UUCP: {sun,ucbvax}!pixar!ph
San Rafael, CA 94913		ARPA: ph%pixar.uucp@ucbvax.berkeley.edu