[GRASS-dev] [INFO] Line simplification algorithm

[Hamish]

tlaronde at polynum.com wrote:
> On Tue, Nov 21, 2006 at 03:31:52PM +1300, Hamish wrote:
> > 
> > "v.prune" in GRASS 5 is essentially unchanged since moving into CVS
> > in 1999:
> > http://freegis.org/cgi-bin/viewcvs.cgi/grass/src/mapdev/v.prune/v.prune.c.diff?r1=1.1&r2=1.3
> 
> I'm talking about the main pruning routing dig_prune() to be found in
> VECTORLIB.
> 
> Since dig_prune dated back 1987, and was unchanged during 10 years it
> is unlikely that it was not correctly doing its work.

Other bugs have survived that long... unlikely but still possible.

> BTW, since I'm using  memories from 3 years ago (I haven't used GRASS
> GPL since 5.0) am I confusing v.prune with another module (v.clean)? 
> But I don't think so.
> I think I used v.rm.dangles (or something like that), v.prune (and
> drop it since the curves disappeared) and v.spag (that was not doing
> as much work as it shall do).

v.clean in GRASS 6 collected v.prune, v.spag, v.rm.dangles, etc in a
single module.
e.g. v.prune -> "v.clean tool=prune"
     v.spag  -> "v.clean tool=break"

 
> I attach the original version of dig_prune.

/* $Id: prune.c,v 1.7 2006/10/31 14:23:31 tlaronde Exp $
 * Copyright 2004 Thierry LARONDE <tlaronde at polynum.com>
 * All rights reserved. 
 * 
 * See the COPYRIGHTS at the root of the source directory.
 *
 *!!!THIS SOFTWARE IS PROVIDED ``AS IS'' WITHOUT ANY WARRANTIES!!! 
 *                     USE IT AT YOUR OWN RISK 
 ********************************************************************/
/* @(#)prune.c	2.1  6/26/87  */

is this in fact the "original version" ?

which is that? from GRASS 4.1 source code? which file?

the earliest I have is 4.3, do you have a link to the 4.1 source code?

The history page on the website says:
"26. October 1999 GRASS 5.0 released under GNU GPL (Baylor University
and Markus Neteler)"

but grass4.3 source code states GPL in the COPYRIGHT file.
I seem to remember Markus saying the full GPL code audit happened for
GRASS 5, but 4.3 source has a "src.nonGPL/" dir already.

What about 4.2 (Baylor)? Is that the first version that mentions the
GPL? The 4.1.5 Linux port?

?

grass43/src/mapdev$ find | grep prune.c
./libes/old_dev/prune.c
./diglib/prune.c
./diglib/prune.c.veryold
./v.prune/prune.c
./v.prune/v.prune.c
./OLDlib/prune.c

grass43/src/mapdev$ \
for FILE in `find | grep prune.c` ; do
   diff /tmp/Thierry_prune.c $FILE | wc -l
done

361 libes/old_dev/prune.c
389 diglib/prune.c
327 diglib/prune.c.veryold
250 v.prune/prune.c
803 v.prune/v.prune.c
319 OLDlib/prune.c

v.prune/prune.c is totally different but the smallest because both files
are small.

I think both versions would need to be run through indent before that
test will give good results.
(eg src/mapdev/OLDlib/prune.c seems similar to your attachment)

OLDlib/prune.c and diglib/prune.c.veryold are almost the same,
(prune.c.veryold has a bugfix that OLDlib doesn't)

# versioning not much help:
grass43$ grep -rI "2.1  6/26/87 " * | grep prune
src/mapdev/libes/old_dev/prune.c:/*  @(#)prune.c        2.1  6/26/87  */
src/mapdev/diglib/prune.c.veryold:/*  @(#)prune.c       2.1  6/26/87  */
src/mapdev/OLDlib/prune.c:/*  @(#)prune.c       2.1  6/26/87  */
src/vector/libes/old_dev/prune.c:/*  @(#)prune.c        2.1  6/26/87  */
src/vector/diglib/prune.c.veryold:/*  @(#)prune.c       2.1  6/26/87  */
src/vector/OLDlib/prune.c:/*  @(#)prune.c       2.1  6/26/87  */



> > grass43/src/mapdev/v.prune/CHANGES:
> > -----------------------------------------------------------------
> > So for the benefit of the grass community, there is a new
> > dig_prune function, commented (in bad english), that should
> > replace src421/src/mapdev/diglib/prune.c (and not only for
> > linux version, the code is no linux dependant)
> > 
> > Also edited: src421/src/mapdev/v.prune/v.prune.c, replacing
> > the comparaison "==" by "<" in line 114 (test for Threshold != 0)
> > A null value just eliminates duplicate points.
> > 
> > The code is shorter, but the source bigger (many comments).
> > 
> > Michel Wurtz    mw at engees.u-strasbg.fr Feb 18, 1998
> > -------------------------------------------------------------------
> 
> That's puzzled me, since the 4.1 version is short, commented and make
> sense. Does something happen between 4.1 and 4.2, that is without a
> track in a CVS (not here?). Did someone mess with the code previously
> to this change?

this is before any CVS control I think, it would depend on discipline of
devels to bump the version number. As we see with Michel Wurtz's changes
above, that didn't always happen.

the modern grass CVS started in Dec 1999 (AFAIK), just after the GPL
audit (AFAIK) and the birth of the GRASS 5 development.
In the 4.3 source there is a "src/mapdev/v.clean/tags" file, so some
earlier version control existed?


> The "not only for linux version" is strange: there is nothing system
> dependant in the original.

I think that statement is just a no-op.


> FWIW, I have fixed v.spag(1). There were two main problems:

(note due to topological nature of GRASS 6 [it is valid for 3D roads
with a bridge not to cross] this takes more thought?)

In GRASS 6 (parts of) v.spag is in lib/vector/Vlib/intersect.c 
Vect_segment_intersection()
 
> 1) To be sure that the program ends, you must ensure that a line is
> whether unchanged but never touched again, or split but resulting in
> another line (not the same or you will enter an infinite loop). There
> were cases where lines were cut in two new lines, a null length one,
> and the remaining, that is the same as the previous;
> 
> 2) Nodes created were not correctly snapped to existing node, leading
> to the creation of several nodes with the exact same coordinates =>
> visually, lines were connected, but not to the same node so without
> snapping nodes areas could not be created.
> 
> There were, too, missing handling of colinear cases.

diff vs GRASS 4.1? or maybe better simple ASCII vector test case?
(Please :)  there have been many fixes since then of course:
http://freegis.org/cgi-bin/viewcvs.cgi/grass6/lib/vector/Vlib/intersect.c

I seem to remember someone seeing #2 in GRASS 6 recently. v.segment?


> v.cutter(1) is an ambitious complex monster. I have chosen to replace
> it with an extended version of v.spag(1) , since v.spag is trying to
> cut a map agains itself when you think at it that is it's a particular
> case of v.cutter.

replaced in GRASS 6 by v.overlay and v.select. Radim did a very nice job
on these I think.


all for now,
Hamish