[GRASS-dev] [INFO] Line simplification algorithm

[tlaronde at polynum.com]

On Mon, Nov 20, 2006 at 04:59:18PM +0100, tlaronde at polynum.com wrote:
> 
> Looking at what I have in KerGIS (that is the original program with Dave
> Gerdes implementation) I'm puzzled... since this _is_ a Douglas/Peuker
> kind of algorithm with some slight modifications that make sense.

To be technically more accurate, I have to explain what I refer to as a
"kind of Douglas/Peuker algorithm".

Strictly speaking it is _not_ a Douglas/Peuker algorithm, since this
very algorithm starts with the both ends of the line and works by
dichotomy. It is very efficient but costly since its big-Oh an
arrangement of the number of vertices.

Dave Gerdes's algorithm is O(n) and is accurate for what it was 
designed for: pruning extra vertices from data coming from human digitizing.
It is what we can call a "tangential" algorithm, mimicking what a
careful and slow human digitizing could do.

It is a "kind" of same algorithm from a high level overview: trying to
rectify a curve by seing if the vertices are in a given width corridor,
with non-local (neighbouring) considerations (it does not consider
adjacent pairs, or triplets).

The original algorithm will discard less points than a Douglas/Peuker,
but shall be efficient for digitized data. Less efficient for vectorized
(raster to vector) due to the noise induced by pixelization.
-- 
Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
                 http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C