[GRASS-dev] [INFO] Line simplification algorithm

[tlaronde at polynum.com]

Hello Hamish,

On Thu, Nov 23, 2006 at 01:11:14PM +1300, Hamish wrote:
> 
> 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"

Well, in this case this is not v.clean since I only used 5.0. Well and I
remember that I was not totally satisfied reading a source from somebody
at [smallest, smallest DBA systems].

>  
> > 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" ?

Yes, don't be misleaded by the header (here the header of the internal
private copy, replaced by the KerGIS Public Licence when appearing in
the public copy). It's just a boilerplate added to the file without
removing any original copyright information.

Here, this was nothing more than this:
/* @(#)prune.c	2.1  6/26/87  */

and it was in src/mapdev/diglib/prune.c in the original (I get the cpio
files form a link from grass.itc.it web site 3 years ago; I don't know
if the link is still there).

And I'm based on official 4.1, the latest CERL original sources I found.

So it seems there has been a whole story before GRASS get into a CVS
(there is a gap between orphaned CERL and reorganized development, I
think 4.3).

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

I think that prune.c.veryold (for you) is the likely candidate, since
there are some bugfixes from OLDlib/prune.c to diglib/prune.c (a
comment, and the particular case for "all but last point in thresh").

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

BTW, I was not criticizing Michel Wurtz's algorithm (I haven't look at
it precisely). I seemed to recall that the version I used was using a
blind orthogonal distance algorithm that was producing non sense. And
since there was discussion about the simplification algorithms I
connected the two and was surprised to find that the original algorithm
(that does not handle the particular case of x = constant, but this
should only overflow and lead to not pruning) was already a sensible
rectification approach.

It will be hard to track back, and perhaps the simplest is to see what
works and what doesn't. If v.prune(1) or another program does not
exhibit the behavior I seem to remember, well the discussion has some
historic interest but that's all ;)

> 
> > 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?)

KerGIS is still 2D and the intersection is for 2D at the present. In
fact 3D is just an extension (principles will remain the same). The
handling of grouping (still categories in GRASS GPL terminology I think)
has to be done (for use in the generalized v.cutter(1)).

> 
> > 
> > 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 can give them of course but it will be slightly complicated by the
fact that I have fixed some problems in the VECTORLIB too. There were 3
distinct values doing snapping, and there was one value used to
compute the angle (which was a fault, leading to inconsistent
"enumeration" of lines connected, leading to areas not created when
they were indeed correct---you saw the problem in v.digit, when looking
at connected lines from a node [debug mode, 'd'] lines being highlighted
counterclockwise and suddenly a leap being made to a not consecutive
line).

I think that the simplest, if someone is interested, would be to compare
directly with the KerGIS sources.

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

Probably. Making the comparison between still a 4.1 format, and the new
vector engine of GRASS GPL for 6.x will be slightly complicated.

Cheers,
-- 
Thierry Laronde (Alceste) <tlaronde +AT+ polynum +dot+ com>
                 http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C