Re: [Algorithms] Draw & fill regular polygon?

[Manuel M. <m.m...@wa...>]

Hi Joel,

> I should know how to do this, but i don't. I only have the ability in my
> system to draw lines (x1,y1,x2,y2)' to a bitmap, or write to the bitmap as
> a byte array. Can someone tell me the stepwise procedure to draw a polygon
> of n sides and then fill it? Having trouble finding anything online that
> doesn't use pre-existing primitives or libraries.

I think the easiest way to fill a convex polygon is to generate horizontal 
spans, and fill them in.
Declare two arrays (e.g. "left" and "right"), which will be used to store the 
horizontal spans of the polygon. Initialize them with max/min of your 
datatype.
Rasterize each segment on the polygon boundary, by stepping along the y-axis. 
and store the corresponding x coordinate. Something like:

	// Caveat: hande horizontal segments, last segment, etc.
	float dX = (float)(boundary[i+1].x - boundary[i].x)/(boundary[i+1].y - 
boundary[i].y);
	float X = boundary[i].x + 0.5;
	for (int y = boundary[i].y; y < max_y; y++)
	{
		X+= dX;
		left[y] = min(left[y], (int)X);
		right[y] = max(right[y], (int)X);
	}

Now, fill in the spans:

	for (y = min_y; y < max_y; y++)
		for (x = left[y]; x <= right[y]; x++)
			put_pixel(x, y, color);  // Do this via memset instead!

hope this helps.

	Manuel