Login | Register
Nerd ParadiseArtisanal tutorials since 1999
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.


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.


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).


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


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


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


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.


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