Blake O'Hare .com

How to Programmatically Draw a Polygon

For some reason you find yourself needing to draw a polygon on a pixel surface given a set of points. Or perhaps even multiple sets of points to draw a compound polygon with gaps in it.

polygon_0.png

Assume the grid is pixels. Sure, it's a pretty small polygon that will end up grainy when we're done. But small is easy to illustrate.

First create a set of "buckets" that correspond to each X-coordinate that spans across the polygon.
polygon_a.png

Next, iterate through each set of points and add each line segment to all the buckets it "spans". If a line segment is vertical, ignore it, because it spans no buckets. Below, I've started with the first line segment (line segment 0-to-1). I indicate this line segment with the starting point (notated as "0" in the bucket).

polygon_b.png

Line 1-2 is vertical so it is ignored. Line 2-3 spans 1 bucket, so I add a "2" to the corresponding bucket.

polygon_c.png

Line 3-4 spans 2, so I add a "3" to those two buckets.

polygon_d.png

Continue on through all 3 of the polygon point sets...

polygon_e.png

Next, go through each bucket and calculate what y-coordinate that line goes through given the x-coordinate for that bucket. Sort them by this value.

polygon_f.png

Once sorted, group them in pairs. Draw a line between each point in each pair and voila, you've got a filled-in polygon.

polygon_g.png