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:
- Given a polyline P, find the furthest point p away from the the line segment joining endpoints of P.
- If p is less than ε away from the line (between the endpoints), then remove all the points except the endpoints.
- Otherwise - split P at p and repeat the algorithm recursively on both new polylines.
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