Final report of GSOC project 'Spatial Indexes'
Hi List! I'm writing this email as a final report of my Google Summer of Code 2008 project for Boost. My project consist in adding some spatial indexing structures to Boost in the context of the Geometry proposal done by Barend Gehrels. Spatial indexes are data structures optimized for spatial oriented queries. The classic index structures (i.e. a binary tree) aren't spatially enabled, they have different ordering criteria but none of them relates to topological properties. The scope of these structures is really wide, from collision detection for games to geometry indexing for GIS software. The original project goals were: - Build a Quadtree. - Build an rTree. - Integrate some previous work from a former GSoC project of a k-d-tree. - Test and document everything. Both indexes are implemented now and everything is tested and documented. The only task that we didn't complete is the k-d-tree integration, because when we analyzed the code it was not ready, and we didn't have the time to finish it. About the results, we made several tests and benchmarks. We tested both indexes with 230.000 objects from GIS data to check the correctness of the implementation, and we made some benchmarks comparing the quadtree vs. rtree and comparing both of them to existing implementation (like GEOS) with very good results. We describe this benchmarks in the documentation offering this as a guide to choose the best index for each use. The code is still beta (or maybe alpha) and not recommended for production use because it is still not tested enough, but if you want to check the actual status you can find it in the following location: https://svn.boost.org/svn/boost/sandbox/SOC/2008/spacial_indexing/ And the docs are at: https://svn.boost.org/svn/boost/sandbox/SOC/2008/spacial_indexing/libs/spati... The future work now is huge. We have some ideas about integrating this in some way to multindexes, and we want to implement also a 'packed' version of the rtree to improve bulk-loading times among another things. Finally, I would like to thank to Boost for allowing me to be part of this year's SOC. And specially to my mentor Hartmut Kaiser for all his help during the program. -- federico j. fernandez
Federico J. Fernández wrote:
Hi List!
I'm writing this email as a final report of my Google Summer of Code 2008 project for Boost.
My project consist in adding some spatial indexing structures to Boost in the context of the Geometry proposal done by Barend Gehrels.
Spatial indexes are data structures optimized for spatial oriented queries. The classic index structures (i.e. a binary tree) aren't spatially enabled, they have different ordering criteria but none of them relates to topological properties.
The scope of these structures is really wide, from collision detection for games to geometry indexing for GIS software.
The original project goals were:
- Build a Quadtree. - Build an rTree. - Integrate some previous work from a former GSoC project of a k-d-tree. - Test and document everything.
I'm very interested in this library. Congratulations on your work I can't wait to take a look. Thanks, Michael Marcin
- Build a Quadtree. - Build an rTree. - Integrate some previous work from a former GSoC project of a k-d-tree. - Test and document everything.
Hi, This is a very interesting project, it's filling an huge gap and soo many projects need to reimplement these structures. I have one early question, have you considered pushing the quadtree and rtree classes into boost::intrusive, or designing them in the spirit of boost::intrusive? The audience who's in need of large spatial databases (the ones who doesn't need it are fine with linear scans) is likely to hunt for performance. IMO boost::intrusive has given a flexibility to c++ containers not available elsewhere, it'd be a clear winner if your quadtree and rtree can be implemented in generic terms. Again, I'm highly looking forward to this library! Best regards, Christian
On Thu, Sep 11, 2008 at 8:43 PM, Christian Holmquist <c.holmquist@gmail.com> wrote:
I have one early question, have you considered pushing the quadtree and rtree classes into boost::intrusive, or designing them in the spirit of boost::intrusive? The audience who's in need of large spatial databases (the ones who doesn't need it are fine with linear scans) is likely to hunt for performance. IMO boost::intrusive has given a flexibility to c++ containers not available elsewhere, it'd be a clear winner if your quadtree and rtree can be implemented in generic terms.
I have a generic n-ary tree library that might be a good starting point for integrating into Intrusive. It already has its own intrusive tree with a regular tree container built on top of that, plus a post order iterator. I've sent a preliminary version to Ion a while ago, but it's since matured beyond that. I'll also have to check if I can make the full code available since it's work related, but so far I've built a Bounding Interval Hierarchy off its foundations. Regardless of how this gets accomplished, I completely agree that the base class for all of these spatial index classes belongs in Intrusive, with Quad-trees, etc built on top in intrusive and non-intrusive flavors. --Michael Fawcett
I have a generic n-ary tree library that might be a good starting point for integrating into Intrusive. It already has its own intrusive tree with a regular tree container built on top of that, plus a post order iterator. I've sent a preliminary version to Ion a while ago, but it's since matured beyond that. I'll also have to check if I can make the full code available since it's work related, but so far I've built a Bounding Interval Hierarchy off its foundations.
Just tell me if you can share it to check it out, i'm very interested in using boost::intrusive. Thanks! -- federico
This is a very interesting project, it's filling an huge gap and soo many projects need to reimplement these structures.
I have one early question, have you considered pushing the quadtree and rtree classes into boost::intrusive, or designing them in the spirit of boost::intrusive? The audience who's in need of large spatial databases (the ones who doesn't need it are fine with linear scans) is likely to hunt for performance. IMO boost::intrusive has given a flexibility to c++ containers not available elsewhere, it'd be a clear winner if your quadtree and rtree can be implemented in generic terms.
Christian, I don't have experience with boost::intrusive, but I'll check it out to see if it fits with the spatial indexes. Thanks for your suggestion! -- federico
Federico J. Fern?ndez wrote:
I'm writing this email as a final report of my Google Summer of Code 2008 project for Boost.
Hi Federico! This looks interesting, and I will try to compare it with my own z-curve implementation soon. Is there any chance that an HTML version of the documentation can be made available somewhere? (Or maybe it already exists and I have missed it...) Phil.
Hi Federico, Great to see the result of this very interesting project! I've compiled and run the tests successfully, and quickly glanced to them to have an idea of its general use. Didn't have much time to dig very far but it seems very simple and effective. I'm glad to see that you successfully used Barend's Geometry Library. FYI, we recently made some modifications on its interface, nothing very complicated from your point of view I guess. Another preview should be proposed soon, for now Barend is off until next week. I'll take a closer look when I have the time. Regards Bruno
I'm glad to see that you successfully used Barend's Geometry Library. FYI, we recently made some modifications on its interface, nothing very complicated from your point of view I guess. Another preview should be proposed soon, for now Barend is off until next week.
Yes, I know that we have to make some changes to the library to be able to work with the Geometry Library latest version. It's in my TODO list! :) Thanks for your interest in the project! -- federico
Hi Federico!
This looks interesting, and I will try to compare it with my own z-curve implementation soon.
Is there any chance that an HTML version of the documentation can be made available somewhere? (Or maybe it already exists and I have missed it...)
You just have to "compile" the Jamfile in the doc/ directory. It will output the HTML documentation. Thanks for your interest in the project..! -- federico
On Thu, Sep 11, 2008 at 2:41 PM, Federico J. Fernández <federico.fernandez@gmail.com> wrote:
- Build a Quadtree. - Build an rTree. - Integrate some previous work from a former GSoC project of a k-d-tree. - Test and document everything.
When you do rectangle queries, I think you should use an output iterator rather than returning a deque like you do in this line from your tutorial: geometry::box<geometry::point_xy<double> > query_box( geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(5.0, 5.0)); std::deque< std::vector<std::string>::iterator > d = q.find(query_box); One, that is a rather heavy return type. Two, you're exposing an implementation detail. I find the following much nicer: geometry::box<geometry::point_xy<double> > query_box( geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(5.0, 5.0)); std::vector< std::vector<std::string>::iterator > d; q.find(query_box, std::back_inserter(d)); I haven't looked at the code, only the docs, so please excuse me if this functionality already exists. --Michael Fawcett
When you do rectangle queries, I think you should use an output iterator rather than returning a deque like you do in this line from your tutorial:
geometry::box<geometry::point_xy<double> > query_box( geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(5.0, 5.0)); std::deque< std::vector<std::string>::iterator > d = q.find(query_box);
One, that is a rather heavy return type. Two, you're exposing an implementation detail. I find the following much nicer:
geometry::box<geometry::point_xy<double> > query_box( geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(5.0, 5.0)); std::vector< std::vector<std::string>::iterator > d; q.find(query_box, std::back_inserter(d));
I haven't looked at the code, only the docs, so please excuse me if this functionality already exists.
I agree 100%. I'm adding this to my improvements list. Thanks for you suggestion. -- federico
Federico J. Fernández (on 11. September 2008 20:42) wrote:
My project consist in adding some spatial indexing structures to Boost in the context of the Geometry proposal done by Barend Gehrels.
Has the work been included in the current preview/proposal of the Geometry Library? Regards, Thomas
Hi Thomas,
My project consist in adding some spatial indexing structures to Boost in the context of the Geometry proposal done by Barend Gehrels.
Has the work been included in the current preview/proposal of the Geometry Library?
Good question. Not yet but will be. For the last preview we were very busy implementing the "concepts" for all geometries, didn't have time left. However it is necessary, I need them myself also, we will revisit the work and spatial indexing will be included. Barend
participants (8)
-
Barend Gehrels -
Bruno Lalande -
Christian Holmquist -
Federico J. Fernández -
Michael Fawcett -
Michael Marcin -
Phil Endecott -
Thomas Klimpel