[GRASS5] Re: GRASS 5.1 vectors ... trees .vs. tables

[Greg Sepesi]

John Gillette wrote:
> 
> Hi Greg,
> 
> I saw your post and had a couple of questions.
> 
> Do dglib and dgtable go "on top" of the vector
> library?  That is, are they independent of how the
> data for the vectors is currently stored?
> 
> I have started reading books on computational geometry
> and have been thinking about some problems that
> Grass currently can't do such as the union of polygons
> (and ultimately whole maps).  I have been thinking
> about how grass stores topology.  I have been studying
> the doubly connected edge list (DCEL)[1].  However,
> it occurs to me that this could be implemented on
> top of and independently of how the data is currently stored.

I think it makes a lot of sense to have one copy of the vertices, that
other structures can index.  I chose path arrays as the structure that
stores the vertices.  There may be better choices, but I like the idea
of making adjacent vertices in a path also adjacent in memory ...
hopefully exploiting cache designs for common tasks such as drawing
paths.  Then I have other structures (e.g., R-tree) that index into that
storage.

> I am also interested in your "conflate" operation.
> How is that going?

Unfortunately I haven't found any literature describing how others have
implemented/attempted map conflation.  I'm approaching it as an exercise
in path correlation: the paths, in different maps, that correlate the
most can share attributes (e.g., labels).  Too soon to tell if this
approach is too simplified.

Greg

> [1] Computational Geometry:Algorithms and Applications 2nd
> edition, de Berg, et al, Springer Verlag, 2000