Reduce number of points in line

Question

I'm searching for algorithms to reduce the LOD of polylines, lines (looped or not) of nodes. In simple words, I want to take hi-resolution coastline data and be able to reduce its LOD hundred- or thousandfold to render it in small-scale.

I found polygon reduction algorithms (but they require triangles) and Laplacian smoothing, but that doesn't seem exactly what I need.

Answer 1

I developed a very simple algorithm, using the distance of a given point to the following points to decide whether it makes sense to include them in the rendering. Depending on current scale you could associate a minimum distance between points required for a transformed model.

Answer 2

When I was looking at turning a Bezier curve into straight line segments, what I ended up doing was defining a maximum distance between the curve and a straight line between two points of the curve. Start with one point being one end-point, slide the other end along the curve, until sliding it any further would exceed the maximum distance. Then do it again, using the second (and so on) point, until you've covered the whole curve.

You should be able to generate multiple LODs by simply increasing the distance allowed between the line segments and your poly-line.

Answer 3

The solution that I've found and quite probably will use, is Ramer-Douglas-Peucker algorithm. It's used in PostGIS

Add: I've published my own implementation in Python

Answer 4

I'm a fan of sorting the points based on the angle that the segments make on either side of the point, then removing the points with the shallowest angle iteratively until you hit some threshold. O(n log(n)) I think, versus the RDP method's O(n^2), and with smaller constants to boot. :)

The angle can even be scaled by the segment lengths (indeed it's easier to compute it this way) if you want to give more weight (desirability) to longer segments.

Given p0, p1, p2, p1's weight would be ((p0 - p1) dot (p2 - p1)), normalize the differences if you don't want to weight by length. (Contrast this to distance-to-line, it is much cheaper, and the results may be identical.)