Re: [boost] Another GGL review

Subject: Re: [boost] Another GGL review
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-11-18 08:38:23

Hi,

There were many questions and discussions about Spatial Indexes last day 
and we want to clarify this from GGL point of view.

Last summer Federico implemented spatial indexes for GGL during the 
GSoC. He spent several months on this contribution and did a very good 
job. The spatial index does its job correctly and is used together with 
in the OpenStreetmap Merkaartor tool. So we're very satisfied with it, 
and no bugs are reported. And I didn't encounter them myself. I 
explicitly state this again because there were complaints about its quality.

We didn't include the spatial index in this submission though, because:
- the performance should be improved
- the interface can be enhanced

> In the context of a Boost library we would surely expect the interface 
> to a spatial index to be quite similar to the interfaces to std:: 
> containers

We want to have it similar to std:: containers, and or Boost Ranges, and 
or Boost Multi Index. We have to work this out and as Luke states, to 
implement it fast and memory efficient, and having exactly the right 
interface, we decided to postpone this and let the current 
implementation live further as an extension.

>
>> To my way of thinking the polygon clipping is the killer app that GGL would provide.
>>     
>
> Yes, I can see this being a killer app for many use-cases, which makes
> GGL very useful to many, even without a spatial index.
>   
Thanks for this. I like to add that GGL is more than polygon clipping 
alone! The most simple and obvious algorithms are all included in a 
generic way: distance, area, point-in-polygon. I think many users could 
profit from that as well, without reinventing the wheel each time. I 
agree that these algorithms are not that difficult, but they are 
implemented here for cartesian, spherical coordinate systems and for 
more geometry types or geometry type pairs, which is not trivial.

> I suggest that the absence of a spatial index should not be a reason 
> for rejecting GGL.  It might be that adding some concepts to support 
> this could be appropriate; for example, Barend, what requirements does 
> the spatial index extension to your union/intersection algorithm 
> have?  Are they expressed as concepts?
A spatial index can be used, in general:
- to index geometries, so independant on any algorithm included in GGL
- to index segments or sub-geometries during some algorithms which would 
profit from it (such as the union/intersection)

The first is done in OpenStreetmap as mentioned above. It can be easily 
live as an extension and you can envision many implementations of these 
spatial indexes, all with different properties with respect to speed, 
memory, worst-case, etc.

The second one could be used in e.g. union/intersection.  It is 
internally not yet expressed as a Policy, a Concept or a Strategy. For 
such a thing, and the various indexes you can have, the interface should 
be carefully thought out.

Regards, Barend