[GRASS-dev] v.prune with Douglas-Peucker

[Markus Metz]

Hello all,

I encountered a few problems while pruning vector boundaries and decided 
to try to update the algorithm. The biggest problem with the old 
algorithm was that it didn't work in latlon. From previous mails to to 
list I got the idea to use the Douglas-Peucker algorithm as implemented 
in gshhs_dp for pruning lines and boundaries. The algorithm in gshhs was 
tailored to latlon, but I wanted it to work in any projection and use 
map units. This is now realized, it works both in latlon and in 
projections with meters or anything else as map units. The attached 
prune.c goes to lib/vector/diglib/prune.c The threshold is the deviation 
of a given point from a straight line connecting the two adjacent points 
and should be not more than half the map resolution. Using insanely 
large thresholds can result in duplicate centroids. In my test map with 
146000 vertices, 3109 centroids and 4294 areas (areas without centroids 
are islands, this is wanted), I got 2 duplicate centroids when the 
threshold was 1000x map resolution, an insane threshold removing over 
80% of the vertices.  The algorithm itself does not change the first and 
last point, so there is no more need to pass a boundary without the 
first and last point to the algorithm. That means that 
vector/v.clean/prune.c can be modified accordingly.

As before, there is a first routine removing duplicate points. Is there 
a reason for duplicate points in lines or boundaries? If not, why are 
they there at all? I converted rasters to vectors extracting areas and 
typically had above 30% duplicate vertices. Working with large vectors 
with millions of vertices, they are clogging up the vector. So something 
for the wish list would be to have line and area vectors without 
duplicate vertices after map conversions.  For the time being, prune 
should be first run with a threshold of 0.0 as before to remove 
duplicate centroids. Then lines and boundaries can be pruned beginning 
with a small threshold and increasing it gently (e.g. next threshold = 
2x previous threshold), until the vector is satisfyingly reduced while 
preserving the desired amount of detail.

So far I tested the new Douglas-Peucker algorithm in different 
projections and it works fine. But I only tested it on my system (FC6 
x86_64, gcc-4.1.1) with grass-6.2.1 and grass-6.3 cvs snapshot from 
12.5.2007. If anybody is interested in testing the new algorithm and 
help make it the new standard for GRASS, please do!

CAUTION: I'm not a programmer, I'm a biologist by training doing GIS and 
remote sensing work, so I can't guarantee for the code. I tried my best.

Markus (not Neteler but Metz)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: prune.c
Type: text/x-csrc
Size: 8456 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/grass-dev/attachments/20070519/6d30ea21/prune.bin