# How to predict the tolerance value that will yield a given reduction with the Douglas-Peucker algorithm?

Note: I'm a programmer, not a mathematician - please be gentle. I'm not even really sure how to tag this question; feel free to re-tag as appropriate.

I'm using the Douglas-Peucker algorithm to reduce the number of points in polygons (in a mapping application). The algorithm takes a tolerance parameter that indicates how far I'm willing to deviate from the original polygon.

For practical reasons, I sometimes need to ensure that the reduced polygon doesn't exceed a predetermined number of points. Is there a way to predict in advance the tolerance value that will reduce a polygon with N points to one with N' points?

-
If I'm not mistaken, the tolerance is only used in the termination criterion. Couldn't you just change the termination criterion to stop when too many points have been added? – Rahul Sep 16 '11 at 18:16
Rahul - That's a good point, can you post that as an answer? – Herb Caudill Sep 17 '11 at 0:48
@Rahul's suggestion is good but make sure that you run the algorithmm in breadth-first order, instead of the easier depth-first order. – lhf Sep 17 '11 at 2:03
@lhf, Herb: You actually have to do it in badness-first order... I've posted an answer which explains the algorithmic details I had vaguely in mind but didn't have time to work out when I first posted my comment. – Rahul Sep 17 '11 at 4:23

Here is a somewhat nontraditional variation of the Douglas-Peucker algorithm.

We will divide a given curve into pieces which are well approximated by line segments (within tolerance $\varepsilon$). Initially, there is only one piece, which is the entire curve.

1. Find the piece $C$ with the highest "deviation" $d$, where the deviation of a curve is the maximum distance of any point on it from the line segment joining its end points.
2. If $d < \varepsilon$, then all pieces have sufficiently low deviation. Stop.
3. Let $p_0$ and $p_1$ be the end points of $C$, and $q$ be the point on $C$ which attains deviation $d$. Replace $C$ with the piece between $p_0$ and $q$, and the piece between $q$ and $p_1$.
4. Repeat.

It should be easy to see how to modify step 2 so that the algorithm produces exactly $n-1$ pieces, i.e. $n$ points, for any given $n$.

Exercises Things I am too lazy to do myself:

• Show that for (almost) any result of the modified algorithm, there is a corresponding tolerance on which Douglas-Peucker would produce the same result.
• Use priority queues for efficient implementation of step 1.
-
+1 for frankness. :D – J. M. Sep 17 '11 at 4:14