Plain English Programming — Smoothing Polygons

This is how we define a polygon in Plain English:

A polygon is a thing with some vertices.

And this is how we define a vertex:

A vertex is a thing with an x coord, a y coord, and a spot at the x.

The part that says “and a spot at the x” overlays the vertex’s x and y coordinates with a spot, just for convenience.

Now this is a page I whipped up in Plain English’s built-in WYSIWYG page editor to describe how we smooth polygons:

And these are the Plain English sentences we use to actually do the job:

To smooth a polygon:
If the polygon is nil, exit.
If the polygon’s vertices’ count is less than 3, exit.
If the polygon is closed,
append the polygon’s first vertex’s next’s spot to the polygon; set a flag.
Put the polygon’s first vertex into a left vertex.
Loop.
If the left vertex’s next is nil, break.
Put the left vertex’s next into a right vertex.
Get a center spot given the left vertex’s spot and the right vertex’s spot.
Insert the center into the polygon after the left vertex.
Put the left vertex’s next into a new vertex.
If the left vertex’s previous is nil, put the right vertex into the left vertex; repeat.
Get another center spot given the left vertex’s previous’ spot and the new vertex’s spot.
Get a difference between the other center and the left vertex’s spot.
Divide the difference by 2.
Add the difference to the left vertex’s spot.
Put the right vertex into the left vertex.
Repeat.
If the flag is not set, exit.
Destroy the polygon’s first vertex given the polygon.
Destroy the polygon’s last vertex given the polygon.

It’s a little more complicated than the picturesque explanation because it has to deal with both open and closed polygons, and with left over vertices when the total number of vertices isn’t evenly divisible by three.

Here are some sample polygons, shown left-to-right (a) in their original state, (b) smoothed once, (c) smoothed twice, and (d) smoothed three times:

The first example shows that you can put a square peg in a round hole, if you smooth it up first. The red line in the final example shows how smoothing can be used to fit a curve to an irregular dataset.

And that, folks, is…

Whoops! I think that looks more natural smoothed:

Thanks for reading. I hope things go “smoothly” for you in the future.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s