[GRASS5] dgtable vector library

[Greg Sepesi]

Hello,

I've posted the dgtable vector library and demo app to 

   http://www.eduneer.com/gad/dg_src.tar.gz  (2.0 Mbytes)

I'll keep it there a few weeks.  

The README is listed below.

- - -

README
08 sep 2003
Greg Sepesi (sepesi at eduneer.com)


Definition
----------
dgtable:     a directed graph structure based upon lookup tables

Directory Contents
------------------
dg:          test data
dg/demo:     test code for exercising dgtable's graphics, search, and
comp. geometry algorithms
dg/dgbezier: least squared error Bezier curve fitting (using Graphics
Gems, ISBN:0122861663)
dg/dgrtree:  R-Tree code (using Toni Gutman, Michael Stonebrakier, and
Daniel Green's work)
dg/dgtable:  dgtable structure and code

Demonstration
-------------
To run the dgtable demonstration, go to the dg/demo directory and
execute

> make
> ./demo

Expected screen output:

building directed graph from '../hypso.ascii' ...
concatenating paths into a second directed graph ...
   1148 paths in 620 connected components before concatenation.
   729 paths in 620 connected components after.
writing and reading second directed graph ...
   4197896 bytes out; 4197896 bytes in
performing some computational geometry on points in path #5 (name:
'140.00') ...
   140 points in path; 11 points in its 2D convex hull.
   160 triangles in its delaunay triangulation.
fitting Bezier curves through concatenated paths ...
   85638 points in 729 paths before curve fitting.
   66594 points in 729 paths after.

Expected file output (see dg/demo/demo.c for context of data dumps): 

trash.convexhull.txt  
trash.curve3.svg  
trash.delaunay.txt  
trash.path2.dg  
trash.path2.txt  
trash.path.txt

Design Intent: a simpler dglib
------------------------------
Looking for an open-source, stand-alone directed graph library for a
Palm OS application, the GRASS 5.1 dglib vector library seemed ideal
even though there was work to be done on a few of dglib's modes. 
Unfortunately after a couple days and several emails, I was not able to
understand enough of dglib to work on it.  Two questions remained.

   Why use a tree for vertex storage?
   Why use two modes for RAM storage (i.e., FLAT and TREE)?

I then started writing dgtable using lookup tables instead of balanced
trees to store vertices, and using just one mode for RAM storage.

Implementation Results: simpler in some cases, but not in others
----------------------------------------------------------------
The interaction of multiple modes is difficult to document for code
designer(s) and unfortunately also difficult to learn for code
maintainers.  However, as far as I can tell, in addition to dglib's two
modes for storing vertices (i.e., FLAT and TREE), it has two modes for
accessing vertices (i.e., TREE and CACHE) and three modes (referred to
as graph versions) for connecting them.  

dgtable benefits from avoiding multiple modes.  dgtable has no need for
a cache mode because it already efficiently accesses vertices in lookup
tables.  dgtable also has only one storage mode and it is analogous to
dglib's FLAT mode.

On the other hand, the lookup tables of dgtable are not as dynamic as
the trees of dglib and this could be a big expense if an application's
directed graph frequently changes.  I suppose a good compromise would be
to change table size in blocks, but I haven't implemented that yet.

Design
------ 
Referring to dg/dgtable/dgtable.h, a dgtable directed graph consists of 

   - a table of paths (e.g., connected points along a road)
   - a table of vertices (i.e., unique path points)
   - a table of intersections (i.e., non-unique path points)
   - an R-Tree table that provides a spatial link to each 3 point
subsection of each path

Presently, the dgtable library applies this data structure in the
following directed graph algorithms (see dg/dgtable/dgsearch.c):

   - depth first search (uni- or bi-directional paths)
   - breadth first search (uni- or bi-directional paths)
   - minimum spanning tree (uni- or bi-directional paths)
   - shortest path search (uni- or bi-directional paths),

the following computational geometry algorithms (see
dg/dgtable/dggeo.c):

   - 2D convex hull
   - 2D Delaunay triangulation,

and the following graphics algorithm (see dg/dgbezier):

   - least squared error Bezier curve fit.

- - -

I'm using dgtable in a couple projects.  If there's interest in using it
in GRASS ver >= 5.1, I'll add the appropriate formatting and headers.

Greg