Geometry Boost List: [ggl] Storing the topology of a Polygon

Subject: [ggl] Storing the topology of a Polygon
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-07-20 20:05:13

Mats Taraldsvik wrote:
> Hi,
> 
> Often in GIS systems, complex geometries (such as polygons), are
> (also) stored as simpler objects (linestrings, circularstrings) to
> reduce redundancy and maintain topology.
> 
> (from the docs, if I read them correctly:)
> 
> * a Polygon contains/points to Rings and Points
> * a Ring (only) contains/points to Points
> 
> - A Ring is constructed from at least one linestring, I can't maintain
> the topology without that information (i.e. identify common
> linestrings). 
> 
> - - -
> 
> Ideally, I would save two polygons + topology by looping through them,
> looping through their rings, and finally looping through the
> linestrings of each ring. If the two polygons share one of the
> linestrings, I need to store this once, and when a Ring
> contains/points to the linestrings it is constructed from, this is
> trivial. (The result: A modification in this shared linestring is
> refleced in both polygons.) 

We faced a similar problem using map overlay for meshing application.  It is pretty trivial to sort all edges of all polygons by geometry and scan the result to find duplicate edges adjacent to eachother in the sorted vector associated with different polygons.  For the linestring issue you would need to walk the edges of polygons writing out a new line string every time the pair of polygons associated with the shared edge changes.  That would be accomplished in linear time once the association was established.  All this should be about 50 loc and not add materially to the overall runtime because it is on the same order as the library algorithms that precede it, but most likely has a smaller constant factor since the work performed is simpler.  It would be a little tricky to generically support the complex data model that includes shared line strings as portions of polygons, but it is concievably possible with enough call backs in the adaptor of your polygon data types to the polygon concept.  I wouldn't reco
mmend that, however, because it would be more code for dubious benefit, unless you have a very clear idea of how to do it.  I have no notion of how well the interface to the data model might support this type of thing.

Regards,
Luke