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-30 19:50:53

Barend,

On 10/29/2011 10:55 PM, Barend Gehrels wrote:
> 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.
>

What about GEOS? One creates the geometry objects in reverse : points -> 
linestrings -> rings -> 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?
>
> 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
>

The calculation was Luke's idea, not mine. I guess my explainations 
aren't very good (and all the talk of topology is kind of tangential to 
the issue, and maybe confusing), and I'm sorry. I'll try again:

What I want to achieve is very simple:

I need to extract a WKT string from my legacy geometry object(s), 
whether that's polygons, linestrings, points etc.

--
The legacy objects are stored in a "tree structure":
Polygons point to their Rings
Rings point to their Linestrings/segments
Linestrings/segments point to their Points
--
Currently I'm using GEOS, but I want to be able to extract the WKT 
without building an intermediate object.
--
As long as I can define boost.geometry to work with pointers, the fact 
that points or segmens can be shared, shouldn't be an issue at all, 
since boost.geometry would only be reading them (not modifying anything).
Mats