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

Maciej Sieczka tutey at o2.pl
Mon May 21 14:31:45 EDT 2007

Markus Metz wrote:

> 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.

I used to experience doubled vertices in v.build.polylines and v.clean
tool=snap output (these bugs are fixed now in both 6.2.2 CVS and 6.3
CVS) but never in r.to.vect output.

Trying to reproduce your problem I run, in spearfish6 location:

$ g.region rast=soils -a
$ r.to.vect input=soils output=soils_v feature=area

$ g.region rast=streams -a
$ r.thin input=streams output=streams_th
$ r.to.vect input=streams_th output=streams_th_v feature=line

but neither yielded doubled vertices. Using GRASS 6.2.2 and 6.3 current
CVS. Could you provide an exact procedure to reproduce your problem?


More information about the grass-dev mailing list