Re: [boost] Geometry and spatial indexes, my opinion

Subject: Re: [boost] Geometry and spatial indexes, my opinion
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-10-09 19:30:31

Mathias Gaunard wrote:
> Wanting to code a simple 3D virtual world, I looked into the recent 
> spatial indexes SOC work, which depends on the proposed geometry library.

Your message has prompted me to finally have a look at Federico's 
spatial index work.

> I don't really get what boost::spatial_index::spatial_index is for. It 
> does nothing but forward everything to the last template parameter.
>
> Instead of writing
> boost::spatial_index::spatial_index<
>      point_type, value_type,
>      boost::spatial_index::rtree<point_type, value_type>
>  > index(args...);
>
> I might as well write
> boost::spatial_index::rtree<point_type, value_type> index(args...);
>
> Also, I think the spatial indexes do not provide enough operations. The 
> only things they allow is putting point => value pairs, retrieving the 
> value associated to a point in O(log n) time (I assume, complexity is 
> not documented), and finding all values within a certain box (in O(log 
> n) too?).
> Many things one typically wants to do with spatial indexes are not possible:
> - Iterate all (points, value) pairs in the index
> - Find the element closest (or k-closest) to some point in space or 
> other element.
> - Find all elements within a certain range of some point in space or 
> other element
> - Find the elements that intersect with a given object (ray tracing, for 
> example, searches for an element that intersects with a ray and that is 
> the closest to its source)
> - Consider only a part of the indexed space (e.g. an area delimited by a 
> range/sphere or box)
> - Being able to index arbitrary objects and not just points
> - Traverse the spatial index as a tree

I certainly agree that all or most of those operations should be provided.

My own observations:

- insert should take a std::pair for consistency with the std::associative_containers.
- Iteration over a (rectangular) range should involve iterators, not 
returning a std::deque.
- The current find(box) results return only the value_type, not the point.
- When I use integer coordinates I get lots of warnings because of /2.0 
in the code.
- Defaults should be provided (or, values should be chosen at runtime) 
for the "fiddle factors".
- Performance is poor; worse than 10x slower than the code that I'm 
currently using.
- Rectangle iteration for rtrees is much slower than that; I suspect 
there's either a complexity problem or a bug.
- There is no need to use shared_ptr to point to child nodes; this is 
probably a major reason for the performance problem.
- In the quadtree, the bounding boxes of parent and child nodes have 
common edges; this should be exploited to reduce the size of the node.

I understand that this is "only" a GSoC project, but it's sad that 
Federico didn't keep in touch with this list while he was working on 
this code.  We could have quickly pointed out problems like the above 
long before the "final report" stage.  (I see no messages here between 
"Congratulations to the Successful Summer of CodeStudents!" on 20080422 
and "Final report of GSOC project 'Spatial Indexes'" on 20080911.)  I'm 
curious to know if Federico's GSoC mentor had reviewed at least the 
interface to the proposed class.

Regards,  Phil.