4
$\begingroup$
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?

  • 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.2011-09-17

1 Answers 1

4

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.