How to reduce set of points?

Question

I have a ordered list of points (lat,long) on a route. I have a ordered list of stops (lat,long). Let's say I have 1000 points and 20 stops. I would like to reduce the 1000 points to something like 100 depending upon which points are more relevant for the route. Like points which induce turns for example.

One way I think I can do this is to cluster around stops and choose points maybe at random. But it still does not seem effective to me. I'm already using the Douglas Peucker algorithm. Besides these any ideas?

Answer 1

You could make use of the Ramer–Douglas–Peucker algorithm to simplify your polyline.

Given an initial complex polyline, this algorithm obtains a new polyline approximating the original with a specified error tolerance e. The points defining the new polyline are a subset of the original.

The algorithm is incremental, starting with the endpoints of the polyline and adding the point furthest from the current approximation at each iteration. The algorithm converges when all remaining points are within a perpendicular distance e of the current approximation.

The algorithm is based on a "divide & conquer" type approach, and thus has an expected complexity of O(n*log(n)) (although the worst-case is O(n^2)).

Due to it's "worst-first" behaviour, the resulting polyline includes the "important" points that define sharp corners, while excluding pseudo-redundant points along flat sections within the tolerance e.