RDP Algorithm?

The powerpoint presentation and published papers are available.from m.visvalingam@dcs.hull.ac.uk Some browsers do not re-display gif images. You need to force this through a refresh/reload or by going bak and then forward again.

Since we are still in the realms of simplification, Kurt and I wondered whether we could use the more widely available RDP (Ramer/Douglas-Peucker) algorithm for sketching. 1D profiles across DEMs do not have the recumbent curves that coastlines tend to have, which make the RDP algorithm trip over itself.

There have been numerous comparisons of the RDP algorithm with others based on isolated 1D lines. However, the comparison of filtered versions of 1D terrain profiles tend to be rather inconclusive. Nevertheless, these plots were useful for finding the cut-off values which gave comparable results for both algorithms. The tolerances yielded a choice of about 5% of DEM cells.

Filtered cells were also plotted against contour plots to pursue context-based evaluations.   The cells filtered using Visvalingam’s algorithm have a noisy dispersed pattern. In comparison, the RDP algorithm produced a cleaner, crisper distribution, which is less cluttered. It also produced more continuous lines across the terrain. This was the plot preferred by everyone, including Kurt and myself.



                                                      Visvalingam                                                 RDP

However, this consensus broke down when it came to selecting between the sketches generated by the two algorithms.

Here is the sketch resulting from using Visvalingam's algorithm for filtering skells. Compare this with the RDP sketch below.

Most people could not tell the difference between the two sketches and, when pressed, chose the RDP sketch. In his thesis, Kurt therefore stated that either algorithm could be used but that he preferred my algorithm because it brought an element of randomness to the sketch.

When I resumed this study in 1998, only three people (our female secretaries) instantly said that there was a difference and preferred my sketch. They felt it had more points on it (which was not so) and that it portrayed the surface better. They did not provide an argument in support of their statements.

I personally felt that the RDP sketch was clumsy compared with the Visvalingam sketch, such as in the portrayal of this spur.

Although there are odd P-strokes that seem to be detached from the terrain surface in the Visvalingam sketch, the mojority of marks bind into a single surface. The terrain surface appears slope into the picture even without perspective projection. In contrast, many marks on the RDP sketch seem to be detached from the surface. The marks on the right edge of the central plateau, for example, look like squiggles on the full sketch. Similar squiqqles can be seen elsewhere on the sketch.

Although the RDP sketch lacked coherence, many people saw the two sketches as similar. It is well known that the perceptual system separates 2D drawings into figure and ground. Just as figure-ground differentiation gives weight to the figure, it could be that misfits are projected into the foreground where they may be studied or ignored. It could be that those who saw the sketches as the same were ignoring the misfits in much the same way in which we look through dirt and raindrops on the window.

These misfits on the RDP sketch occur where the algorithm has mislocated important breaks of slope. If this is the case, than other extreme point methods for generating DEMs may also be picking the wrong points