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 polyline would be split at this point.

*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