issue with Ramer–Douglas–Peucker algorithm while drawing a line

2
votes

I am developing a painting application for the iOS and to get smooth lines i apply the Ramer–Douglas–Peucker algorithm of the samples points.

The algorithm works on the whole vector of points and the result changes as points are added. It causes the result curve to "jump" while user paints.

Is there a known solution to this problem?

2
algorithmgraphics
Can you describe the problem in more detail? Does the curve "jump" because the result given by the algorithm when the user draws, say, ten points is different from the result when the user draws the eleventh point? If you could perhaps give a visual example of the problem that would be helpful. – Jordan Running
Exactly, a new point can change even one of the first points. It makes sense, because each new point changes the distances, and so the recursion in the algorithm. I wonder if there are easy ways to bypass this problem – Erik Sapir

2 Answers

2
votes

I've never implemented or used this algorithm, but I can think of two possible solutions:

  1. Apply the algorithm to discrete sections of the line. That is, wait until the user has drawn 10 points, then run the algorithm on points 0..9. Then wait until the user has drawn the next 10 points and run the algorithm on points 10..19, and so on. One possible caveat is that it could create side-effects at points 10, 20, etc., but I really don't know if it would be noticeable to the user.

  2. Wait until the user is done drawing, then run the algorithm once on the whole line. I've seen this approach used in apps before.

Both of these have the advantage that you're running the algorithm on each point no more than twice (and exactly once in the latter case), whereas if you run the algorithm every time a point is added you end up running it on every previous point every time you add a point, which could have a performance penalty.

Like I said, this isn't an area of expertise for me, but I hope it gives you some ideas.

2
votes

I doubt this can be avoided at all, for a simple reason: the algorithm cannot guess the future points.

Imagine that you draw the first two points; obviously you will keep them. Now move to a third point. If R-D-P tells you to discard the middle point, you may not because that would cause a jump. And so on. Disallowing the jumps implies that you disallow any deletion !

Maybe you can lessen the psychological effect by drawing both the raw curve, which remains stable, and the smoothed one.

This said, R-D-P maybe not be the best approach for smoothing.