# Nerd Paradise

Artisanal tutorials since 1999
Most recent Linked List
(It's NP's webcomic)

Grand Theft Crouton
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.