Monday, December 20, 2010

The Douglas–Peucker line simplification algorithm

Another classic geometry related algorithm is the Douglas–Peucker line simplification  algorithm. Often in a GIS application, one needs to reduce the complexity of a given entity. I.e., there is no much sense in rendering a river in a zoomed out map, with the same precision that would be required if the map was zoomed in.

Given n points that represents a polyline and a threshold ε, the algorithm would create an approximation of the original polyline by dropping points that are less than ε distance away from the polyline. More formally, the algorithm can be described as follows:
  1. Given a polyline P, find the furthest point p away from the the line segment joining endpoints of P.
  2. If p is less than ε away from the line (between the endpoints), then remove all the points except the endpoints.
  3. Otherwise - split P at p and repeat the algorithm recursively on both new polylines.
In the following illustration, (c) is the furthest point, and since it's distance is larger than ε, the polyline would be split at this point.

The complexity of the algorithm is O(n^2). Notice, that there is an improvement to the algorithm that uses a convex hull to decrease the worst case running time. We start our Haskell implementation by defining the primitive types, point and segment along with a function to compute the dot product of two vectors, and a function to compute points distance

Next we define a function for computing the distance between a point and a segment.

And now, for the algorithm itself

Finally, we try our program on a given input

No comments:

Post a Comment