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

Subject: [ggl] Storing the topology of a Polygon
From: Mats Taraldsvik (mats.taraldsvik)
Date: 2011-10-29 20:06:39

Barend, Luke, list,

Sorry for the (-very-) late reply. I'm currently a geomatics student, 
but I am assesing boost.geometry for my (future) employer (and out of 
personal interest/curiosity).

On 07/20/2011 11:59 PM, Barend Gehrels wrote:
> Hi Mats,
>
> On 20-7-2011 20:26, 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.
>
> Yes, some do it like this, for example, ESRI coverages. Most (most 
> spatial databases, shapefiles, MapInfo) do not do this anymore.
>

I understand that the spatial databases (like postgis) doesn't maintain 
topology internally by itself. However, when working with the objects 
built from the database, I need to be able too loop through them in a 
tree-like manner (Polygons->Rings->Linestrings/Segments/Arcs->Points).

An example:

- Polygon 1, Polygon 2

- Polygon 1: Linestrings 1, 2,3

- Polygon 2: Linestrings 4, 2, 3

(and linestrings are made up of points etc...)

The point is that Linestring 2 have a lot of metadata that is common, 
and should not be stored redundantly. Storing redundant linestrings 
would both be, well, redundant, as well as providing room for 
errors/inconsistency. When managing e.g. land ownership, this is 
obviously very important.

>>
>> (from the docs, if I read them correctly:)
>>
>> * a Polygon contains/points to Rings and Points
>> * a Ring (only) contains/points to Points
>
> Right. These are the provided models. But more is possible.
>
>>
>> - 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.) 
>
>
> Boost.Geometry does not offer topology out of the box. However, it 
> does offer concepts. So a Ring is is a vector of points, but you can 
> attach information to it. You can create your own models (including 
> topologic information, ID's, SRID, names, etc etc) and register this 
> or adapt this to the concepts. It will then work with Boost.Geometry.
>
> Besides this, if your model (e.g. a Ring) implements Boost.Range, you 
> can create a ring which consists of linestrings of multiple sources. 
> So you can share those linestrings. This will be much more complex to 
> implement, and to be honest, exactly this I've never implemented or 
> worked out, but I think it should be feasable. As long as it provides 
> Boost.Range behaviour, and is registered with Boost.Geometry, it will 
> work.
>

So could I modify a Ring to also point to a range of e.g. segments, 
which points to the appropriate Linestrings/Circularstrings, which 
points to the Points, while the Ring's original range somehow loops 
through the points directly (through this hierarchy), for maintaining 
compability with boost.geometry's algorithms?

> Good point. I'm curious.
>
> Regards, Barend
>
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl

On 07/21/2011 12:00 AM, Simonson, Lucanus J wrote:
> 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 re
commend 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
>
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl

The main problem with this approach (I may not have understood it 
correctly) is that I would have to load the entire contents (or a large 
portion) of the database into my program to calculate the common 
linestrings and points, but there are several (if not tens or hundreds) 
of gigabytes of data. I then need to pair the correct metadata with the 
correct linestrings.

Regards,
Mats