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

Subject: [ggl] Storing the topology of a Polygon
From: Barend Gehrels (barend)
Date: 2011-10-30 02:09:56

Hi Mats,

On 29-10-2011 17:10, Mats Taraldsvik wrote:
> 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.

I understand you but Boost.Geometry is, out of the box, not working like 
this. Like most Geometry libraries I know of.

>
>>
>>
>> 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?

Yes, as said, I think it should be feasable but did not work it out.

>
> On 07/21/2011 12:00 AM, Simonson, Lucanus J wrote:
>> 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 recommend 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
> 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.

If I understand this correctly (and snipped the message in the right 
way), you want to calculate common borders? That is not what I intended 
to inform. If you have a database with no common borders but topology, 
you should query it in the right way and get your rings (in the right 
order) such that maybe in memory they are stored twice, but in the 
database only once, and that you don't have to figure out common borders 
yourself.

Regards, Barend