[GRASS-dev] v.clean tool=prune - 'thresh' interpreted wrong?

Maciej_Sieczka2 · October 2, 2006, 7:10pm

There is a line:

  $ echo "L 4 1
   10 10
   20 10
   30 10
   40 10
   1 1" | v.in.ascii -n out=line format=standard

So there are 4 vertices and the distance between each 2 following is
10. Then I don't understand why the:

$ v.clean input=line output=line_pruned type=line tool=prune
thresh=1

removes ALL the vertices!:

  $ v.out.ascii line_pruned format=standard
  ORGANIZATION:
  DIGIT DATE:
  DIGIT NAME: shoofi
  MAP NAME:
  MAP DATE: Mon Oct 2 20:51:52 2006
  MAP SCALE: 1
  OTHER INFO:
  ZONE: 0
  MAP THRESH: 0.000000
  VERTI:
  L 2 1
   10 10
   40 10 <- WHY ARE THE TWO OTHER GONE ???
   1 1

I declared thresh=1, the distance between vertices is 10 - so none
should be removed, but all are! And the same happens with all the lower
thresholds until thresh=0.03.

???

v.clean man says: "prune: remove vertices in threshold". Maybe I don't
understand what the threshold means in this case?

Maciek

P.S.

Any clarification will be highly appreciated. I've been writing a
script that uses pruning and I would like to publish it, but this is
puzzling me bad and I don't know whether it's a bug or my mistake. Thanks.

H_B · October 3, 2006, 2:05am

Maciej Sieczka wrote:

There is a line:

  $ echo "L 4 1
   10 10
   20 10
   30 10
   40 10
   1 1" | v.in.ascii -n out=line format=standard

So there are 4 vertices and the distance between each 2 following is
10. Then I don't understand why the:

  $ v.clean input=line output=line_pruned type=line tool=prune
  thresh=1

removes ALL the vertices!:

  $ v.out.ascii line_pruned format=standard
  ORGANIZATION:
  DIGIT DATE:
  DIGIT NAME: shoofi
  MAP NAME:
  MAP DATE: Mon Oct 2 20:51:52 2006
  MAP SCALE: 1
  OTHER INFO:
  ZONE: 0
  MAP THRESH: 0.000000
  VERTI:
  L 2 1
   10 10
   40 10 <- WHY ARE THE TWO OTHER GONE ???
   1 1

I declared thresh=1, the distance between vertices is 10 - so none
should be removed, but all are! And the same happens with all the lower
thresholds until thresh=0.03.

???

v.clean man says: "prune: remove vertices in threshold". Maybe I don't
understand what the threshold means in this case?

what if there is some angle between the points? e.g.

G6> v.in.ascii -n out=line format=standard << EOF
L 4 1
10 10
20 5
30 7.5
40 10
1 1
EOF

Hamish

Maciej_Sieczka2 · October 3, 2006, 12:08pm

Hamish wrote:

Maciej Sieczka wrote:

  $ echo "L 4 1
   10 10
   20 10
   30 10
   40 10
   1 1" | v.in.ascii -n out=line format=standard

So there are 4 vertices and the distance between each 2 following is
10. Then I don't understand why the:

  $ v.clean input=line output=line_pruned type=line tool=prune
  thresh=1

I declared thresh=1, the distance between vertices is 10 - so none
should be removed, but all are! And the same happens with all the lower
thresholds until thresh=0.03.

what if there is some angle between the points? e.g.

v.in.ascii -n out=line format=standard << EOF
L 4 1
10 10
20 5
30 7.5
40 10
1 1
EOF

$ v.clean input=line output=line2_pruned type=line tool=prune thresh=1

$ v.out.ascii line2_pruned format=standard | awk 'NR>10'
L 3 1
10 10
20 5
40 10
1 1

The thresh=1, but v.clean prunes the 3rd vertex "30 7.5", which as far
from the other 2 vertices as ~10.3! I don't get it.

Any hints Radim?

Maciek

mlennert · October 3, 2006, 12:23pm

Maciej Sieczka wrote:

Hamish wrote:

Maciej Sieczka wrote:

  $ echo "L 4 1
   10 10
   20 10
   30 10
   40 10
   1 1" | v.in.ascii -n out=line format=standard

So there are 4 vertices and the distance between each 2 following is
10. Then I don't understand why the:

  $ v.clean input=line output=line_pruned type=line tool=prune
  thresh=1

I declared thresh=1, the distance between vertices is 10 - so none
should be removed, but all are! And the same happens with all the lower
thresholds until thresh=0.03.

what if there is some angle between the points? e.g.

v.in.ascii -n out=line format=standard << EOF
L 4 1
10 10
20 5
30 7.5
40 10
1 1
EOF

$ v.clean input=line output=line2_pruned type=line tool=prune thresh=1

$ v.out.ascii line2_pruned format=standard | awk 'NR>10'
L 3 1
10 10
20 5
40 10
1 1

The thresh=1, but v.clean prunes the 3rd vertex "30 7.5", which as far
from the other 2 vertices as ~10.3! I don't get it.

Doesn't

20 5
30 7.5
40 10

Define a straight line ? I would guess that the prune tool prunes all "unneccessary" nodes on a straight line, i.e. any node which is not necessary to define the line, and this whatever the threshold.

The threshold only applies in cases of change of direction (i.e. angles).

Just another example of the need for much more documentation for v.clean, including example diagrams like the one for the rmsa tool.

Moritz

Markus_Neteler1 · October 3, 2006, 12:33pm

On Tue, Oct 03, 2006 at 02:23:56PM +0200, Moritz Lennert wrote:
...

Doesn't

20 5
30 7.5
40 10

Define a straight line ? I would guess that the prune tool prunes all
"unneccessary" nodes on a straight line, i.e. any node which is not
necessary to define the line, and this whatever the threshold.

The threshold only applies in cases of change of direction (i.e. angles).

Just another example of the need for much more documentation for
v.clean, including example diagrams like the one for the rmsa tool.

Fully agreed... but let me reiterate that a different pruning
algorithm might be the best solution (e.g. Douglas-Peucker which
is found as C code on the GMT site). The current one doesn't even work
in LatLong.

Markus

Maciej_Sieczka2 · October 3, 2006, 12:56pm

Markus Neteler wrote:

On Tue, Oct 03, 2006 at 02:23:56PM +0200, Moritz Lennert wrote:

I would guess that the prune tool prunes all
"unneccessary" nodes on a straight line, i.e. any node which is not
necessary to define the line, and this whatever the threshold.

The threshold only applies in cases of change of direction (i.e. angles).

Just another example of the need for much more documentation for
v.clean, including example diagrams like the one for the rmsa tool.

Fully agreed...

Markus,

Agreed regarding what?

Moritz just supposes but he is not sure. And if you look into my
original email you'll that he's wrong:

1. a *straight* line, consisted of 4 vertices, at regular intervals of
10
2. thresh>0.03 prunes all vertices (besides the nodes of course)
3. thresh<=0.03 prunes none

Then Moritz's idea is wrong.

And I need to know exactly how the thresh in prune works, as I'm using
it for my work. The result will be a script that I'm going to publish.
Please - if anybody knows, tell me. I'd love to update the manual
accordingly.

Maciek

Markus_Neteler1 · October 3, 2006, 1:06pm

On Tue, Oct 03, 2006 at 02:56:18PM +0200, Maciej Sieczka wrote:

Markus Neteler wrote:
> On Tue, Oct 03, 2006 at 02:23:56PM +0200, Moritz Lennert wrote:

>> I would guess that the prune tool prunes all
>> "unneccessary" nodes on a straight line, i.e. any node which is not
>> necessary to define the line, and this whatever the threshold.
>>
>> The threshold only applies in cases of change of direction (i.e. angles).
>>
>> Just another example of the need for much more documentation for
>> v.clean, including example diagrams like the one for the rmsa tool.

> Fully agreed...

Markus,

Agreed regarding what?

... regarding that more documentation is needed.

...

And I need to know exactly how the thresh in prune works, as I'm using
it for my work. The result will be a script that I'm going to publish.
Please - if anybody knows, tell me. I'd love to update the manual
accordingly.

Apparently it can be only reverse engineered (luckily it's FOSS).
I was not too happy with my attempts to use the prune algorithm,
I don't think that it works reasonable well.

But this is an old story:
http://grass.itc.it/pipermail/grassuser/1995-January/012655.html
http://grass.itc.it/pipermail/grassuser/2006-July/035373.html
http://grass.itc.it/pipermail/grassuser/2006-August/035529.html

The first mail indicates that the problem is known and wasn't
resolved so far. Time to switch to another algorithm

Markus

mlennert · October 3, 2006, 1:13pm

Maciej Sieczka wrote:

Markus Neteler wrote:

On Tue, Oct 03, 2006 at 02:23:56PM +0200, Moritz Lennert wrote:

I would guess that the prune tool prunes all "unneccessary" nodes on a straight line, i.e. any node which is not necessary to define the line, and this whatever the threshold.

The threshold only applies in cases of change of direction (i.e. angles).

Just another example of the need for much more documentation for v.clean, including example diagrams like the one for the rmsa tool.

Fully agreed...

Markus,

Agreed regarding what?

I think Markus responded to my remark on lack of documentation.

Moritz just supposes but he is not sure. And if you look into my
original email you'll that he's wrong:

1. a *straight* line, consisted of 4 vertices, at regular intervals of
10
2. thresh>0.03 prunes all vertices (besides the nodes of course)
3. thresh<=0.03 prunes none

Then Moritz's idea is wrong.

And I need to know exactly how the thresh in prune works, as I'm using
it for my work. The result will be a script that I'm going to publish.
Please - if anybody knows, tell me. I'd love to update the manual
accordingly.

Check

http://freegis.org/cgi-bin/viewcvs.cgi/grass6/lib/vector/diglib/prune.c?rev=HEAD&content-type=text/vnd.viewcvs-markup

There is an explanation of the algorithm at the beginning.

Moritz

mlennert · October 3, 2006, 1:21pm

Markus Neteler wrote:

On Tue, Oct 03, 2006 at 02:56:18PM +0200, Maciej Sieczka wrote:

Markus Neteler wrote:

On Tue, Oct 03, 2006 at 02:23:56PM +0200, Moritz Lennert wrote:

I would guess that the prune tool prunes all "unneccessary" nodes on a straight line, i.e. any node which is not necessary to define the line, and this whatever the threshold.

The threshold only applies in cases of change of direction (i.e. angles).

Just another example of the need for much more documentation for v.clean, including example diagrams like the one for the rmsa tool.

Fully agreed...

Markus,

Agreed regarding what?

... regarding that more documentation is needed.
...

And I need to know exactly how the thresh in prune works, as I'm using
it for my work. The result will be a script that I'm going to publish.
Please - if anybody knows, tell me. I'd love to update the manual
accordingly.

Apparently it can be only reverse engineered (luckily it's FOSS).
I was not too happy with my attempts to use the prune algorithm,
I don't think that it works reasonable well.

But this is an old story:
http://grass.itc.it/pipermail/grassuser/1995-January/012655.html
http://grass.itc.it/pipermail/grassuser/2006-July/035373.html
http://grass.itc.it/pipermail/grassuser/2006-August/035529.html

The first mail indicates that the problem is known and wasn't
resolved so far. Time to switch to another algorithm

Michel's changes date from 1998 and were apparently written for 4.2.1, so there was change since then. Don't know if that resolved the problem though... Nor which algorithm is better.

Moritz

Maciej_Sieczka2 · October 3, 2006, 3:43pm

Moritz Lennert wrote:

http://freegis.org/cgi-bin/viewcvs.cgi/grass6/lib/vector/diglib/prune.c?rev=HEAD&content-type=text/vnd.viewcvs-markup

There is an explanation of the algorithm at the beginning.

Thanks, I should have looked into the source code first. My only (poor)
excuse is being a non-programmer and "mentally handicapped" due to my
disgraceful pre-Linux/FOSS times ;).

Moritz suggested that maybe "the threshold only applies in cases of
change of direction (i.e. angles)". Please note there is no any
reference to angles or direction in the code or comments. It seems the
threshold refers to distance only.

There is a following comment:

* thresh - the distance that a string must wander from a straight
* line before another point is selected.

As I understand it, this means that if my vertcices are on a straight
line, at intervals of 10, only a thresh of 10 or more should prune
them. But, as you can see in my original example, any thresh>=0.03
prunes them. Do I missunderstand sthing (I'm not sure what the
"straight line" means here)?

So we have 2 possibilities:

1. If in opposite to my interpretation of the source and manual,
angles/directions DO have something to do with the pruning thresh,
please somebody knowledgeable tell me what is that relation, so I can
fix the part of the manual, that reads "prune: remove vertices in
threshold from lines (...)".

2. If the pruning thresh doesn't depend on angles/directions, how do I
understand the fact that any thresh>=0.03 prunes points which are at
intervals of 10 on a straight line?

Maciek

CCing Mr. Michel Wurtz in case he is still out there under this email,
maybe.

Gordon_Whitmore · October 3, 2006, 3:43pm

How do I stop getting the "GRASS" e-mails.......
Thanks
----- Original Message ----- From: "Maciej Sieczka" <tutey@o2.pl>
To: <grassuser@grass.itc.it>; <grass-dev@grass.itc.it>; "Radim Blazek" <radim.blazek@gmail.com>
Cc: "Markus Neteler" <neteler@itc.it>; "Moritz Lennert" <mlennert@club.worldonline.be>
Sent: Tuesday, October 03, 2006 9:56 AM
Subject: Re: [GRASS-dev] Re: [GRASS-user] v.clean tool=prune -'thresh' interpreted wrong?

Markus Neteler wrote:

On Tue, Oct 03, 2006 at 02:23:56PM +0200, Moritz Lennert wrote:

I would guess that the prune tool prunes all
"unneccessary" nodes on a straight line, i.e. any node which is not
necessary to define the line, and this whatever the threshold.

The threshold only applies in cases of change of direction (i.e. angles).

Just another example of the need for much more documentation for
v.clean, including example diagrams like the one for the rmsa tool.

Fully agreed...

Markus,

Agreed regarding what?

Moritz just supposes but he is not sure. And if you look into my
original email you'll that he's wrong:

1. a *straight* line, consisted of 4 vertices, at regular intervals of
10
2. thresh>0.03 prunes all vertices (besides the nodes of course)
3. thresh<=0.03 prunes none

Then Moritz's idea is wrong.

And I need to know exactly how the thresh in prune works, as I'm using
it for my work. The result will be a script that I'm going to publish.
Please - if anybody knows, tell me. I'd love to update the manual
accordingly.

Maciek

_______________________________________________
grass-dev mailing list
grass-dev@grass.itc.it
http://grass.itc.it/mailman/listinfo/grass-dev

mlennert · October 3, 2006, 4:26pm

Maciej Sieczka wrote:

Moritz Lennert wrote:

http://freegis.org/cgi-bin/viewcvs.cgi/grass6/lib/vector/diglib/prune.c?rev=HEAD&content-type=text/vnd.viewcvs-markup

There is an explanation of the algorithm at the beginning.

Thanks, I should have looked into the source code first. My only (poor)
excuse is being a non-programmer and "mentally handicapped" due to my
disgraceful pre-Linux/FOSS times ;).

Moritz suggested that maybe "the threshold only applies in cases of
change of direction (i.e. angles)". Please note there is no any
reference to angles or direction in the code or comments. It seems the
threshold refers to distance only.

There is a following comment:

* thresh - the distance that a string must wander from a straight
* line before another point is selected.

As I understand it, this means that if my vertcices are on a straight
line, at intervals of 10, only a thresh of 10 or more should prune
them. But, as you can see in my original example, any thresh>=0.03
prunes them. Do I missunderstand sthing (I'm not sure what the
"straight line" means here)?

So we have 2 possibilities:

1. If in opposite to my interpretation of the source and manual,
angles/directions DO have something to do with the pruning thresh,
please somebody knowledgeable tell me what is that relation, so I can
fix the part of the manual, that reads "prune: remove vertices in
threshold from lines (...)".

2. If the pruning thresh doesn't depend on angles/directions, how do I
understand the fact that any thresh>=0.03 prunes points which are at
intervals of 10 on a straight line?

To plead in Markus' direction: there is a 3rd possibility:

3. Forget about the current pruning implementation and push the integration of another algorithm (Douglas-Peucker). (I know you are working on a script, but could this wait until this is done ? Maybe if you push hard enough someone will "just do it" - Dylan mentioned it as a potentially "fun" project: http://grass.itc.it/pipermail/grassuser/2006-August/035529.html and actually links to an implementation in c++, which actually looks like more or less usable C to me).

Markus you mentioned the source code on the GMT site. Could you be more precise on where to find it ?

Moritz

Markus_Neteler1 · October 3, 2006, 4:35pm

Moritz Lennert wrote on 10/03/2006 06:26 PM:

Maciej Sieczka wrote:

Moritz Lennert wrote:

http://freegis.org/cgi-bin/viewcvs.cgi/grass6/lib/vector/diglib/prune.c?rev=HEAD&content-type=text/vnd.viewcvs-markup

There is an explanation of the algorithm at the beginning.

Thanks, I should have looked into the source code first. My only (poor)
excuse is being a non-programmer and "mentally handicapped" due to my
disgraceful pre-Linux/FOSS times ;).

Moritz suggested that maybe "the threshold only applies in cases of
change of direction (i.e. angles)". Please note there is no any
reference to angles or direction in the code or comments. It seems the
threshold refers to distance only.

There is a following comment:

* thresh - the distance that a string must wander from a straight
* line before another point is selected.

As I understand it, this means that if my vertcices are on a straight
line, at intervals of 10, only a thresh of 10 or more should prune
them. But, as you can see in my original example, any thresh>=0.03
prunes them. Do I missunderstand sthing (I'm not sure what the
"straight line" means here)?

So we have 2 possibilities:

1. If in opposite to my interpretation of the source and manual,
angles/directions DO have something to do with the pruning thresh,
please somebody knowledgeable tell me what is that relation, so I can
fix the part of the manual, that reads "prune: remove vertices in
threshold from lines (...)".

2. If the pruning thresh doesn't depend on angles/directions, how do I
understand the fact that any thresh>=0.03 prunes points which are at
intervals of 10 on a straight line?

To plead in Markus' direction: there is a 3rd possibility:

3. Forget about the current pruning implementation and push the
integration of another algorithm (Douglas-Peucker). (I know you are
working on a script, but could this wait until this is done ? Maybe if
you push hard enough someone will "just do it" - Dylan mentioned it as
a potentially "fun" project:
http://grass.itc.it/pipermail/grassuser/2006-August/035529.html
and actually links to an implementation in c++, which actually looks
like more or less usable C to me).

Markus you mentioned the source code on the GMT site. Could you be
more precise on where to find it ?

Sure:
http://www.ngdc.noaa.gov/mgg/shorelines/data/gshhs/version1.3/
-> gshhs_1.5_src.tbz
-> gshhs/gshhs_dp.c

Markus

PS: Let's reduce CC'ing to the DEV list to not spam hundreds of users
with this (now very detailed) thread.

Maciej_Sieczka2 · October 3, 2006, 4:41pm

Moritz Lennert wrote:

Maciej Sieczka wrote:

Moritz Lennert wrote:

http://freegis.org/cgi-bin/viewcvs.cgi/grass6/lib/vector/diglib/prune.c?rev=HEAD&content-type=text/vnd.viewcvs-markup

There is an explanation of the algorithm at the beginning.

Thanks, I should have looked into the source code first. My only
(poor) excuse is being a non-programmer and "mentally handicapped"
due to my disgraceful pre-Linux/FOSS times ;).

Moritz suggested that maybe "the threshold only applies in cases
of change of direction (i.e. angles)". Please note there is no any
reference to angles or direction in the code or comments. It
seems the threshold refers to distance only.

There is a following comment:

* thresh - the distance that a string must wander from a straight
* line before another point is selected.

As I understand it, this means that if my vertcices are on a
straight line, at intervals of 10, only a thresh of 10 or more
should prune them. But, as you can see in my original example, any
thresh>=0.03 prunes them. Do I missunderstand sthing (I'm not sure
what the "straight line" means here)?

So we have 2 possibilities:

1. If in opposite to my interpretation of the source and manual,
angles/directions DO have something to do with the pruning thresh,
please somebody knowledgeable tell me what is that relation, so I
can fix the part of the manual, that reads "prune: remove vertices
in threshold from lines (...)".

2. If the pruning thresh doesn't depend on angles/directions, how
do I understand the fact that any thresh>=0.03 prunes points which
are at intervals of 10 on a straight line?

To plead in Markus' direction: there is a 3rd possibility:

3. Forget about the current pruning implementation and push the
integration of another algorithm (Douglas-Peucker). (I know you are
working on a script, but could this wait until this is done ?

I should have done that script by yesterday (no kidding, just laughing).

Maybe if you push hard enough someone will "just do it" - Dylan
mentioned it as a potentially "fun" project:
http://grass.itc.it/pipermail/grassuser/2006-August/035529.html
and actually links to an implementation in c++, which actually looks
like more or less usable C to me).

Sure it would be a good addition to Grass, but:

1. I need a tool to remove the vertices from a line based on a given
threshold (understood as a distance from one vertex to another).
According to v.clean manual it should be able to do it, but it's not.
(I think I know how to workaround it by v.out.acii | awk | v.in.ascii.
So I should be OK.)

2. This is a bug or a lacking documention, so either should be fixed,
no matter what other pruning algorithm is added to Grass.

3. We can't remove any functionality in Grass 6, only add new.

Markus you mentioned the source code on the GMT site. Could you be
more precise on where to find it ?

Maciek

Dylan_Beaudette1 · October 3, 2006, 6:04pm

On Tuesday 03 October 2006 09:35, Markus Neteler wrote:

Moritz Lennert wrote on 10/03/2006 06:26 PM:
> Maciej Sieczka wrote:
>> Moritz Lennert wrote:
>>> http://freegis.org/cgi-bin/viewcvs.cgi/grass6/lib/vector/diglib/prune.c
>>>?rev=HEAD&content-type=text/vnd.viewcvs-markup
>>>
>>>
>>> There is an explanation of the algorithm at the beginning.
>>
>> Thanks, I should have looked into the source code first. My only (poor)
>> excuse is being a non-programmer and "mentally handicapped" due to my
>> disgraceful pre-Linux/FOSS times ;).
>>
>> Moritz suggested that maybe "the threshold only applies in cases of
>> change of direction (i.e. angles)". Please note there is no any
>> reference to angles or direction in the code or comments. It seems the
>> threshold refers to distance only.
>>
>> There is a following comment:
>>
>> * thresh - the distance that a string must wander from a straight
>> * line before another point is selected.
>>
>> As I understand it, this means that if my vertcices are on a straight
>> line, at intervals of 10, only a thresh of 10 or more should prune
>> them. But, as you can see in my original example, any thresh>=0.03
>> prunes them. Do I missunderstand sthing (I'm not sure what the
>> "straight line" means here)?
>>
>> So we have 2 possibilities:
>>
>> 1. If in opposite to my interpretation of the source and manual,
>> angles/directions DO have something to do with the pruning thresh,
>> please somebody knowledgeable tell me what is that relation, so I can
>> fix the part of the manual, that reads "prune: remove vertices in
>> threshold from lines (...)".
>>
>> 2. If the pruning thresh doesn't depend on angles/directions, how do I
>> understand the fact that any thresh>=0.03 prunes points which are at
>> intervals of 10 on a straight line?
>
> To plead in Markus' direction: there is a 3rd possibility:
>
> 3. Forget about the current pruning implementation and push the
> integration of another algorithm (Douglas-Peucker). (I know you are
> working on a script, but could this wait until this is done ? Maybe if
> you push hard enough someone will "just do it" - Dylan mentioned it as
> a potentially "fun" project:
> http://grass.itc.it/pipermail/grassuser/2006-August/035529.html
> and actually links to an implementation in c++, which actually looks
> like more or less usable C to me).
>
> Markus you mentioned the source code on the GMT site. Could you be
> more precise on where to find it ?

Sure:
http://www.ngdc.noaa.gov/mgg/shorelines/data/gshhs/version1.3/
-> gshhs_1.5_src.tbz
-> gshhs/gshhs_dp.c

Markus

Now that doesn't look like to difficult a snippet of code to port to GRASS.
Only issue would be to make it less dependent on input being in lat/long :

int Douglas_Peucker_i (int x_source, int y_source, int n_source, double
band, int index)
/* x_source: Input coordinates in micro-degrees */
/* y_source: */
/* n_source: Number of points */
/* band: tolerance in kilometers */
/* index: output co-ordinates indices */

then adapting it to GRASS data types / structs

hmmmm...

--
Dylan Beaudette
Soils and Biogeochemistry Graduate Group
University of California at Davis
530.754.7341

H_B · October 4, 2006, 1:52am

Markus Neteler wrote:

On Tue, Oct 03, 2006 at 02:56:18PM +0200, Maciej Sieczka wrote:
> Markus Neteler wrote:
> > On Tue, Oct 03, 2006 at 02:23:56PM +0200, Moritz Lennert wrote:
>
> >> I would guess that the prune tool prunes all
> >> "unneccessary" nodes on a straight line, i.e. any node which is
> >not > necessary to define the line, and this whatever the
> >threshold. >
> >> The threshold only applies in cases of change of direction (i.e.
> >angles). >
> >> Just another example of the need for much more documentation for
> >> v.clean, including example diagrams like the one for the rmsa
> >tool.
>
> > Fully agreed...
>
> Markus,
>
> Agreed regarding what?

... regarding that more documentation is needed.

...
> And I need to know exactly how the thresh in prune works, as I'm
> using it for my work. The result will be a script that I'm going to
> publish. Please - if anybody knows, tell me. I'd love to update the
> manual accordingly.

Apparently it can be only reverse engineered (luckily it's FOSS).
I was not too happy with my attempts to use the prune algorithm,
I don't think that it works reasonable well.

But this is an old story:
http://grass.itc.it/pipermail/grassuser/1995-January/012655.html
http://grass.itc.it/pipermail/grassuser/2006-July/035373.html
http://grass.itc.it/pipermail/grassuser/2006-August/035529.html

The first mail indicates that the problem is known and wasn't
resolved so far. Time to switch to another algorithm

so the existing tool acts like:
v.clean tool=simplify_without_geographic_change"
? (removes redundant verticies in a line (angle==0))

and the Douglas-Peucker method could be called tool=generalize ?

??

to me the meaning of "prune" is ambiguous.

v.clean --help:
prune: remove vertices in threshold from lines and boundaries, boundary
is pruned only if topology is not damaged (new intersection, changed
attachement of centroid), first and last segment of the boundary is
never changed

this sounds like it is meant do "generalize".

???

need to do some tests & create screen shots (eg v.voronoi help page)
to be sure.

Hamish

mlennert · October 4, 2006, 8:50am

Maciej Sieczka wrote:

Moritz Lennert wrote:

Maybe if you push hard enough someone will "just do it" - Dylan
mentioned it as a potentially "fun" project: http://grass.itc.it/pipermail/grassuser/2006-August/035529.html
and actually links to an implementation in c++, which actually looks
like more or less usable C to me).

Sure it would be a good addition to Grass, but:

1. I need a tool to remove the vertices from a line based on a given
threshold (understood as a distance from one vertex to another).
According to v.clean manual it should be able to do it, but it's not.
(I think I know how to workaround it by v.out.acii | awk | v.in.ascii.
So I should be OK.)

To echo Hamish' question: Do you need to remove vertices from lines without changing the form of the line, or do you want to generalize the form of the line (in the way that is shown here: http://mpa.itc.it/markus/como2006/img9.html ?

2. This is a bug or a lacking documention, so either should be fixed,
no matter what other pruning algorithm is added to Grass.

It actually also seems to be an ambiguity as to what pruning actually means:

- remove unnecessary nodes, or
- generalize

?

3. We can't remove any functionality in Grass 6, only add new.

We cannot change the interface of modules, but we can do what we want in terms of algorithms used behind this interface. Especially if the current algorithm is buggy.

Moritz

Maciej_Sieczka2 · October 4, 2006, 9:14am

Moritz Lennert wrote:

To echo Hamish' question: Do you need to remove vertices from lines
without changing the form of the line, or do you want to generalize the
form of the line (in the way that is shown here:
http://mpa.itc.it/markus/como2006/img9.html ?

The latter. I want to remove all the vertices that are distant from the
line starting node not more than the give thresh. A line:

x--o1-o2-->----o3--x

"x" - node
"o" - vertex
">" - line direction
"-" - 1 length unit

thresh=3 would remove o1, thresh=5 the o1 and o2 and so on

2. This is a bug or a lacking documention, so either should be fixed,
no matter what other pruning algorithm is added to Grass.

It actually also seems to be an ambiguity as to what pruning actually
means:

- remove unnecessary nodes, or
- generalize

Using that terminology - according to current Grass documentation
(v.clean manual and the source code comments) v.clean tool=prune means
"generalize".

Maciek

mlennert · October 4, 2006, 9:26am

Maciej Sieczka wrote:

Moritz Lennert wrote:

To echo Hamish' question: Do you need to remove vertices from lines
without changing the form of the line, or do you want to generalize the
form of the line (in the way that is shown here:
http://mpa.itc.it/markus/como2006/img9.html ?

The latter. I want to remove all the vertices that are distant from the
line starting node not more than the give thresh. A line:

x--o1-o2-->----o3--x

"x" - node
"o" - vertex
">" - line direction
"-" - 1 length unit

thresh=3 would remove o1, thresh=5 the o1 and o2 and so on

This sounds like something still different, as you make it dependent on the starting node. I don't think that the prune tool was ever thought to work this way.

Moritz

Maciej_Sieczka2 · October 4, 2006, 9:53am

Moritz Lennert wrote:

Maciej Sieczka wrote:

Moritz Lennert wrote:

To echo Hamish' question: Do you need to remove vertices from lines
without changing the form of the line, or do you want to generalize the
form of the line (in the way that is shown here:
http://mpa.itc.it/markus/como2006/img9.html ?

The latter. I want to remove all the vertices that are distant from the
line starting node not more than the give thresh. A line:

x--o1-o2-->----o3--x

"x" - node
"o" - vertex
">" - line direction
"-" - 1 length unit

thresh=3 would remove o1, thresh=5 the o1 and o2 and so on

This sounds like something still different, as you make it dependent on
the starting node.

Still we don't know how the thresh works for pruning.

I don't think that the prune tool was ever thought to work this way.

You don't know how it works. Then how do you know how it doesn't work ?

Getting back to my original post.

The line:

$ echo "L 4 1
   10 10
   20 10
   30 10
   40 10
   1 1" | v.in.ascii -n out=line format=standard

Imagine it as:

x-o1-o2-x

"x" - node
"o" - vertex
"-" - 5 length units

$ v.clean input=line output=line_pruned type=line tool=prune thresh=0.04

removes o1,o2. Anything bigger does the same. Anything smaller doensn't
remove any.

Why? Should it be like that or not?

Maciek