[boost] Final report of GSOC project 'Spatial Indexes'

Subject: [boost] Final report of GSOC project 'Spatial Indexes'
From: Federico J. Fernández (federico.fernandez_at_[hidden])
Date: 2008-09-11 14:41:33

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/spatial_index/doc/

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