Smoothening complex polygons - Ramer–Douglas–Peucker algorithm | Hacker News Reader

Smoothening complex polygons - Ramer–Douglas–Peucker algorithm

en.wikipedia.org

30 pointsideamonk14 comments

Another interesting discussion on it - http://stackoverflow.com/questions/1849928/how-to-intelligen...

Not sure that's better than the Wiki article, but the PostGIS mention is really handy if you're generalizing data for maps or to make paths from GPS data.

Protip: If you set the epsilon low enough, the PostGIS implementation has a good chance of repairing invalid geometries, even when ArcInfo can't.

I'm sure they exist, so can anyone point to extensions of the concept to piecewise-Bézier curves (as opposed to piecewise linear).

This isn't directly Bezier related, but you may find some inspiration here. Talks about piecewise linear, bilinear, double linear, biquadratic, cubic, bicubic, piecewise cubic and biquintic.

This is a great link and helped me conceptualize and workout bicubic interpolation. Have fun :)

Wait, where's the link?

Doh! Don't know how that didn't paste in: http://www.geocomputation.org/1999/082/gc_082.htm

You're going to have to delete a lot of points or move a lot of points, so it's probably not any faster than doing a regular run through RDP and then interpolating. Interpolating is easy enough. The bottleneck (at least in the Objective-C++ implementation I have) is pow and sqrt, which are pretty hard to avoid. If you want to make it faster the best way to do it is to remove the interior points of each line segment in the polygon you're working with (before you run it through RDP). The easiest way to do that is to keep track of what direction you're extracting the points from, from whatever you've already edged (or however you're doing it) since most blob extraction algorithms return every point around the edge of each polygon. If you think about it you just need to throw away everything except for the corners.

That's assuming you're working from bitmap images, which I guess is not necessarily the case. If you're working from a sparse set of points to begin with and you're not getting the performance you need you're going to have find other ways to speed it up obviously.

Was happy to see this come across HN. I had bookmarked several notes and a PHP implementation of this. I am planning on using this to simplify the number of points defining a particular path on a google map, for a small preview map. Some of my data is > 1 meg for a long route, so trimming is important.

Check out a live PHP demo: http://www.fonant.com/demos/douglas_peucker/algorithm

This would be interesting/useful for smoothing geospatial polygons (eg, KML).

Dmitri Lebedev had a public domain python script up at ryba4.com but the site seems to be down.

It's handy, I've used it for KML generation and a command line SVG path simplify tool.

Google maps won't download a file larger than 3MB so simplifying can be important.

At a previous job I implemented a tool to smooth map areas and at the same time preserve the topology between the areas (e.g. there would be no gaps between Texas and Louisiana after the smoothing). I had a lot of fun writing it.

That sounds very useful. How did you do it? Could you share it?

Did you create an algorithm that would smooth polygons the same way going clockwise or counter-clockwise so that the shared boundaries would be simplified the same way? Or did your algorithm take into account the entire topology?

It was indeed very useful :). Unfortunately I cannot share too much due to NDA (not that I consider what I did cutting edge...). But I will say that I couldn't take the entire topology into account due to limitations with the host SDK (I was working on a plug-in for a leading vector graphics application).

GEOS has an implementation of it http://docs.djangoproject.com/en/dev/ref/contrib/gis/geos/#d...

and postgis lets you simplify in sql query itself.

Reply on news.ycombinator.com