Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
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?

share|improve this question
1  
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
1  
@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
1  
@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

1 Answer 1

up vote 4 down vote accepted

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.
share|improve this answer
    
+1 for frankness. :D –  J. M. Sep 17 '11 at 4:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.