# Get thee gone, my polygon

March 31, 2009 7:40 AM Subscribe

I've got a polygon of

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

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

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

*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

_{1},y

_{1}) = (x

_{n},y

_{n})?

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

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

Sounds like an interesting problem! Is the original data from pixel boundaries?

posted by pmdboi at 8:24 AM on March 31, 2009

- 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).
- There are a couple pages concerning polygon simplification; the second one in particular looks the most promising.

Sounds like an interesting problem! Is the original data from pixel boundaries?

posted by pmdboi at 8:24 AM on March 31, 2009

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, 2009

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, 2009

also, I would suggest combining the tag "beziercurves", and add "geometry" and "curvefitting".

posted by onalark at 8:48 AM on March 31, 2009

posted by onalark at 8:48 AM on March 31, 2009

Everything mentioned sounds promising!

posted by soma lkzx at 8:51 AM on March 31, 2009

**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, 2009

**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, 2009

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, 2009

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, 2009

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, 2009

posted by onalark at 9:02 AM on March 31, 2009

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, 2009 [1 favorite]

posted by soma lkzx at 9:15 AM on March 31, 2009 [1 favorite]

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, 2009

I guess the Matlab map toolbox has coastline and other geographic data. Neat.

posted by fantabulous timewaster at 6:30 PM on March 31, 2009

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, 2009

posted by onalark at 7:43 AM on April 1, 2009

PROBLEM SOLVED, MADE STARTLINGLY BEAUTIFUL: Triptrop NYC

posted by soma lkzx at 7:08 AM on April 21, 2009

posted by soma lkzx at 7:08 AM on April 21, 2009

This thread is closed to new comments.

posted by fritley at 8:12 AM on March 31, 2009 [1 favorite]