[GRASS5] detri license clarified (new hope for geom)

GRASS GRASS developer
1

Hi Guys,

after a couple of weeks of discussion the license and code issues
of libes/geom code, I have refined the findings saved in
grass/src/libes/geom/README

Here is the main part:

| Ernst is the principal author of detri, which includes lia, sos, basic.

| The latest detri code is available from:
| http://www.geocities.com/mucke/GeomDir/detri.html
|
| detri_2.9www.tar.gz now has clarified texts showing
| that Ernst's part of it (everything except part of basic) is free
| software!

Andreas:
We can go out now and use the detri code for geom if this helps us
in any way. We have to remove some of the "basic" code as I do not want to
go through the hassle of contacting Steve Summit.

  Bernhard

--
Professional Service around Free Software (intevation.net)
The FreeGIS Project (freegis.org)
Association for a Free Informational Infrastructure (ffii.org)
FSF Europe (www.fsfeurope.org)

2

Hi,

does this mean that the geom lib must be moved to src.nonGPL?
This would mean that s.geom and v.geom can no longer be used.

I had a very superficial glance at geom and detri, but i can not say how
much work it will be to adapt s.geom and v.geom to this library.
And i am not able to do that.

Another option would be to use the gts library
(http://gts.sourceforge.net) for this purpose. But from the mailing list
i conclude that the delaunay triangulation in this library is broken. If
this is fixed it should be comparatively simple to make a s.delaunay,
v.delaunay and s.hull etc. (or a single s.geom and v.geom module resp.)
from this. Don't know how complicated it will be to make the Voronoi
diagram/Thiessen polygons from this (thiessen polygons and delaunay
trinagulation are complementary).

But i am confused: s.delaunay and s.voronoi are currently in
src.contrib/PURDUE/s.voronoi, but the html-man-page describes another
program of that name from Jo Wood, which i can not find (no bin, no
src). The Program from Jo Wood is able to generate VRML output and works
in 2.5D with elevation scaling.

The people working on the vector library should decide if we should
include the detri library. As far as i remember the detri library is 3D
and may be faster than gts (where the delaunay triangulation is only
2D). But i am totally clueless, so that i can not recommend anything.

cu,

Andreas

Bernhard Reiter wrote:

Hi Guys,

after a couple of weeks of discussion the license and code issues
of libes/geom code, I have refined the findings saved in
grass/src/libes/geom/README

Here is the main part:

| Ernst is the principal author of detri, which includes lia, sos, basic.

| The latest detri code is available from:
| http://www.geocities.com/mucke/GeomDir/detri.html
|
| detri_2.9www.tar.gz now has clarified texts showing
| that Ernst's part of it (everything except part of basic) is free
| software!

Andreas:
We can go out now and use the detri code for geom if this helps us
in any way. We have to remove some of the "basic" code as I do not want to
go through the hassle of contacting Steve Summit.

        Bernhard

--
Professional Service around Free Software (intevation.net)
The FreeGIS Project (freegis.org)
Association for a Free Informational Infrastructure (ffii.org)
FSF Europe (www.fsfeurope.org)

    ---------------------------------------------------------------

               Part 1.2 Type: application/pgp-signature

--
Andreas Lange, 65187 Wiesbaden, Germany, Tel. +49 611 807850
Andreas.Lange@Rhein-Main.de - A.C.Lange@GMX.net

----------------------------------------
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo@geog.uni-hannover.de with
subject 'unsubscribe grass5'

3

On Tue, Dec 05, 2000 at 04:39:31PM +0100, Andreas Lange wrote:

Hi,

does this mean that the geom lib must be moved to src.nonGPL?
This would mean that s.geom and v.geom can no longer be used.

I had a very superficial glance at geom and detri, but i can not say how
much work it will be to adapt s.geom and v.geom to this library.
And i am not able to do that.

Another option would be to use the gts library
(http://gts.sourceforge.net) for this purpose. But from the mailing list
i conclude that the delaunay triangulation in this library is broken. If
this is fixed it should be comparatively simple to make a s.delaunay,
v.delaunay and s.hull etc. (or a single s.geom and v.geom module resp.)
from this. Don't know how complicated it will be to make the Voronoi
diagram/Thiessen polygons from this (thiessen polygons and delaunay
trinagulation are complementary).

Perhaps "gts" would be a better choice fpr the long run as it is widely
adopted for many projects (like LAPACK/BLAS)?

But i am confused: s.delaunay and s.voronoi are currently in
src.contrib/PURDUE/s.voronoi, but the html-man-page describes another

This is from: James Darrell McCauley, Purdue University

program of that name from Jo Wood, which i can not find (no bin, no
src). The Program from Jo Wood is able to generate VRML output and works
in 2.5D with elevation scaling.

Well, Jo's code is at:
http://www.geog.le.ac.uk/assist/grass/source/

No copyright statement on the page. I have met him this summer, I am
sure he agrees to use his code (I could contact him).
Jo has left to London recently.

The people working on the vector library should decide if we should
include the detri library. As far as i remember the detri library is 3D
and may be faster than gts (where the delaunay triangulation is only
2D). But i am totally clueless, so that i can not recommend anything.

David and Radim (and others), please advise us!

Markus

----------------------------------------
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo@geog.uni-hannover.de with
subject 'unsubscribe grass5'

4

On Tue, Dec 05, 2000 at 04:39:31PM +0100, Andreas Lange wrote:

does this mean that the geom lib must be moved to src.nonGPL?

Yes, unless somebody reworks it to use detri.
Markus: can you move geom to src.nonGPL for grass5.0beta9!

(Oh and btw: Please do not include the src.nonGPL in the source
and default build tar.)

This would mean that s.geom and v.geom can no longer be used.

Yes.

Another option would be to use the gts library
(http://gts.sourceforge.net) for this purpose.

detri seems to be a working library, I cannot say anything about gts.

  Bernhard
--
Professional Service around Free Software (intevation.net)
The FreeGIS Project (freegis.org)
Association for a Free Informational Infrastructure (ffii.org)
FSF Europe (www.fsfeurope.org)

5

Markus Neteler wrote:

On Tue, Dec 05, 2000 at 04:39:31PM +0100, Andreas Lange wrote:
> Hi,
>
> does this mean that the geom lib must be moved to src.nonGPL?
> This would mean that s.geom and v.geom can no longer be used.
>
> I had a very superficial glance at geom and detri, but i can not say how
> much work it will be to adapt s.geom and v.geom to this library.
> And i am not able to do that.
>
> [...]

> The people working on the vector library should decide if we should
> include the detri library. As far as i remember the detri library is 3D
> and may be faster than gts (where the delaunay triangulation is only
> 2D). But i am totally clueless, so that i can not recommend anything.
David and Radim (and others), please advise us!

For a later version of the vector library we want to have support for 3d
vector maps directly in the vector API itself. The idea is to use
triangulated surfaces as the geometric primitive. So a suitable library
would have to be able to do 3d triangulations, also would have to be
implemented as a well-exposed API - most of the triangulation hacks seem
to be end-use programs. I suspect that whatever is used will have to be
customised to some extent.

To create a suitable surface, triangulations should

* be constrained so that triangles are moderately well-behaved, but this
should be flexible

* show some relationship between local cell size and relief, for example
larger triangles in regions of low curvature. But then - how is point
selection done?

There is another public domain (sensu stricto) implementation called
dewall, which does 3d (http://vcg.iei.pi.cnr.it/DVRunstruct.html). The
documentation (dewall.pdf) gives some benchmarks for different
algorithms.

In sum, I don't have a clear idea yet how to get the details of the
vector library, but we need a triangulation API. If it's not Detri, it
would be something else, perhaps the precise method is not critical.

David

----------------------------------------
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo@geog.uni-hannover.de with
subject 'unsubscribe grass5'

6

Hi David,

i highly agree that an API is needed instead of the modules hacks right
now.

At least i need the s.geom and v.geom functionality right now.
I did some superficial tests with s.delaunay and s.voronoi. s.delaunay
seems to work ok, but s.voronoi has problems with some point
distributions. With the bugsites points from the spearfish data set i
can not generate a correct voronoi diagram. This seems to me a problem
of the implementation of the sweepline algorithm.

Let me summarize what is needed (only as a first proposal from users
standpoint):

delaunay triangulation in 2d and 3d from sites and vectors (points)
voronoi diagram in 2d from sites and vector (points)
convex hull in 2d (and in 3d?) from sites and vector (points)
min-max angle triangulation (?)
min-max slope triangulation (?)
min-max height triangulation (?)
calculation of centroid points for polygons (for m.clump or something
similar).

All the functions should work on grass data structures for points and
vectors. This will require some more conceptual work as it can not
always be assumed that the data can be loaded in memory in one hunk. At
least the hacks used right now (writing the points in a specific format
to a temp file, processing this and re-importing again) can not be used
with library functions.

Sorry that i can not present something more elaborate. But i think that
a library for computational geometry is urgently needed.

Andreas

David D Gray wrote:

For a later version of the vector library we want to have support for 3d
vector maps directly in the vector API itself. The idea is to use
triangulated surfaces as the geometric primitive. So a suitable library
would have to be able to do 3d triangulations, also would have to be
implemented as a well-exposed API - most of the triangulation hacks seem
to be end-use programs. I suspect that whatever is used will have to be
customised to some extent.

To create a suitable surface, triangulations should

* be constrained so that triangles are moderately well-behaved, but this
should be flexible

* show some relationship between local cell size and relief, for example
larger triangles in regions of low curvature. But then - how is point
selection done?

There is another public domain (sensu stricto) implementation called
dewall, which does 3d (http://vcg.iei.pi.cnr.it/DVRunstruct.html). The
documentation (dewall.pdf) gives some benchmarks for different
algorithms.

In sum, I don't have a clear idea yet how to get the details of the
vector library, but we need a triangulation API. If it's not Detri, it
would be something else, perhaps the precise method is not critical.

--
Andreas Lange, 65187 Wiesbaden, Germany, Tel. +49 611 807850
Andreas.Lange@Rhein-Main.de - A.C.Lange@GMX.net

----------------------------------------
If you want to unsubscribe from GRASS Development Team mailing list write to:
minordomo@geog.uni-hannover.de with
subject 'unsubscribe grass5'