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

[Markus Metz]

Maciej Sieczka wrote:
> 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
>
>   
use
$ r.to.vect -s input=soils output=soils_vs feature=area
soils_vs has 30337 duplicate vertices
without smoothing corners I also don't get duplicate vertices

> $ g.region rast=streams -a
> $ r.thin input=streams output=streams_th
> $ r.to.vect input=streams_th output=streams_th_v feature=line
>
>   
this vector doesn't have any duplicate vertices, neither has 
streams_th_vs created with
$ r.to.vect -s input=streams_th output=streams_th_vs 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?
>
> Maciek
>
>   
My main issue was that I wanted to offer a new mehtod for line/boundary 
simplification based on the Douglas-Peucker algorithm. These duplicate 
vertices are not much of a problem, the only increase the size of a 
vector which can become a problem when working on large regions with a 
high resolution. The real problem is that the old pruning method 
produces funny results and doesn't work in latlon.

Run
$ v.in.region output=region type=area

create new location for spearfish in latlon
import the vector region from spearfish60
set region to match this vector
import soils_vs from spearfish60

prune vector with
$ v.clean input=soils_vs at user1 output=soils_vs_double type=boundary 
tool=prune thresh=0

this removes duplicate vertices (old and new prune.c)

now prune
$ v.clean input=soils_vs_double at user1 output=soils_vs_old type=boundary 
tool=prune thresh=0.001

results is nothing pruned. Try higher thresholds, I tried thresh=10, 
still nothing is pruned. Now try the new Douglas-Peucker algorithm with 
thresh=0.001 (this is decimal degrees according to the projection) and 
have a look at the result. I hope you like it.

Sorry for the long answer!

Markus