[GRASS-dev] [INFO] Line simplification algorithm
tlaronde at polynum.com
tlaronde at polynum.com
Mon Nov 20 13:09:42 EST 2006
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
More information about the grass-dev
mailing list