Subject: Re: [boost] Another GGL review
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-11-18 08:38:23
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::
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk