Get thee gone, my polygon

March 31, 2009 7:40 AM

I've got a polygon of n points. How can I simplify out noisy edges?

I have a bunch of ordered (x,y) pairs that make nice little polygons, but there're just too much data to be manageable. It'd be nice to average out some of the rougher bits into less points.

Most of the edges look like the heaviside step function, a.k.a. someone walking city blocks. Checking (x_i+1,y_i+1) vs. (x_i-1,y_i-1) and the rest of the diagonals could work out, but I'd really be into a more elegant/general algorithmic solution.

Less importantly but possibly related, let's say I wanted to give these polygons smooth sides. Do I drop bezier curve after bezier curve? I also just met splines on wikipedia - should I just apply this natural cubic spline curve algorithm with (x₁,y₁) = (x_n,y_n)?

I'm currently working on this in Ruby, if that matters, but am open to pretty much anything.

posted by soma lkzx to science & nature (12 comments total)

You might consider thinking about the problem like this: As you go along the polygon edge you want to merge any collection of nearly-colinear points. A set of points are nearly-colinear if when you draw a line from the first in the set to the last in the set, the intermediate points are all within a distance tolerance T of that line. When you find such a set, you can discard the intermediate vertices and simplify your polygon. You can experiment with different tolerances. If you have "stairsteps" of length 1, a tolerance of sqrt(2)/2 will eliminate them.
posted by fritley at 8:12 AM on March 31 [1 favorite has favorites]

So there are a couple different approaches that you can take.

1. If the polygon is roughly convex, you can use a convex hull algorithm to get the bounding polygon, which will probably have fewer vertices than your data set. There's probably a canned algorithm for that kind of thing floating around for Ruby (hey, like this one).
2. There are a couple pages concerning polygon simplification; the second one in particular looks the most promising.

The Bezier path solution you propose would probably just give you a tightly wavy shape instead of a jagged one; not much better.

Sounds like an interesting problem! Is the original data from pixel boundaries?
posted by pmdboi at 8:24 AM on March 31

What a cool problem! As people here have suggested, your ideal simplification is going to depend on what the polygons represent.

Also, a bunch of points do not a polygon make! Think of the four points forming a square and an arbitrary point in the center. I count at least four different ways to combine those points to form a simple polygon, though only one way to form a convex polygon.

As for transforming the points into a smooth object, that's an interesting (and hard) problem. There are some well known algorithms for drawing an ellipsoid that covers some set of points, but I think you are more interested in something with a fairly arbitrary path. I think you've got the right idea with cubic splines, though your level of overfit will be through the roof if you use all the points.

It would help to see a few sample data files and what your idea of what the polygons you simplify to would look like.
posted by onalark at 8:43 AM on March 31

also, I would suggest combining the tag "beziercurves", and add "geometry" and "curvefitting".
posted by onalark at 8:48 AM on March 31

Everything mentioned sounds promising!

pmdboi: The original data is actually travel time, but it ends up being basically the same - I'm grouping similar values, doing some edge detection, and then trying to draw around the boundaries so the result is more like an isarithmic map than a heat map. I'll post to Projects once I'm done.
posted by soma lkzx at 8:51 AM on March 31

onalark: I'll drop you an email with some sample data. Anyone else who wants to see a sample, email's in my profile.
posted by soma lkzx at 8:54 AM on March 31

Hmnn, so you have say a 100x100 grid, and on that grid, every pixel has some value? And what you're trying to do is color all the pixels with similar values the same color, and group them into similar objects?

Sounds like a contour fitting problem more than anything else. MATLAB can automatically turn data like this into a contour map, if you can send me the raw map of pixel data, that might be the best start.
posted by onalark at 8:59 AM on March 31

Is this the sort of thing you're trying to do? countourfm function in MATLAB Mapping Toolbox
posted by onalark at 9:02 AM on March 31

If MATLAB can automatically turn this into a contour map, looks like I'm about to get engaged to a piece of software. You've got some data in your inbox.
posted by soma lkzx at 9:15 AM on March 31

Octave also makes contour maps.

I guess the Matlab map toolbox has coastline and other geographic data. Neat.
posted by fantabulous timewaster at 6:30 PM on March 31

Just to follow up from a private email discussion with soma, we decided that the free mapping toolbox available through SciPy is his best bet. I am awaiting the results of this project with eager anticipation :)
posted by onalark at 7:43 AM on April 1

PROBLEM SOLVED, MADE STARTLINGLY BEAUTIFUL: Triptrop NYC
posted by soma lkzx at 7:08 AM on April 21