[boost] Geometry and spatial indexes, my opinion

Subject: [boost] Geometry and spatial indexes, my opinion
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2008-10-07 18:52:12

Hi,

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

I have to admit I was fairly disappointed.
So I'm going to put some critics, some quite harsh maybe, along with 
some ramblings about what I would have liked to have.
Note that I am no geometry or space indexing expert, so what I say may 
be perfectly silly.

For starters, I think those libraries should be dimension agnostic and 
generic. Geometry not only has a strong 2D bias, but the documentation 
also says geometry::box only works with point_xy (and point_ll).
Since it is used everywhere in spatial index, that means it's unusable 
on 3D.

The geometry documentation doesn't clearly state what a geometry::box 
is. Is it (assuming 2D) any rectangle or only axis-aligned rectangles?
In case it is just any rectangle, it mind be interesting to introduce a 
new type for axis-aligned ones, which can always be defined from two 
points whatever the dimension (well, at least it seems enough for 3D, 
I'm not good at projecting in other dimensions to see if that'd work).
I suppose the spatial index interface expects axis-aligned boxes, so 
it's fairly important to clarify what we're talking about.

Apart from that, there is also lots of point_xy-dependent code in 
spatial indexes. Also the quadtree implementation isn't dimension 
agnostic in particular (it should have 2^n children nodes, and not 4).
I don't really get why it uses shared_ptr everywhere either (is it 
supposed to support COW or something?)

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 believe there is no need to clutter the interface with a lot of 
functions, most algorithms can be implemented generically as free functions.
Giving a read-only tree interface to all spatial indexes ought to be 
enough to implement all algorithms. A spatial index, after all (correct 
me if I'm wrong), is nothing else but a tree that partitions space, 
where every node defines a partition of space that includes all of its 
children (which might overlap or not). Subtrees should be full-fledged 
spatial indexes (so that I can perform a search in a subtree), albeit 
read-only.
Apart from that they should allow insertion and removal of object => 
value pairs.

Quadtrees and r-trees should be fairly easy to work with: they both 
partition space into axis-aligned boxes (which are even cubes in quadtrees).

As for allowing all kinds of objects to be stored instead of just 
points, that should be possible by using generic distance and 
intersection functions.
The real difference is that the same object could eventually be in 
multiple places in the tree, because it spans over multiple space 
partitions. Whenever you put an object in the tree or split a partition, 
however, it would be necessary to calculate in which partitions to put 
the object, whereas with points you only have to find the one partition.

Of course, some cases can be specialized and optimized, like 
axis-aligned boxes in a R-tree, which can directly be used as partitions 
and thus never span across multiple ones.
I find it weird having a different interface for R-trees and Quadtrees. 
Indeed, one can only put points in a quadtree while in a r-tree you can 
put boxes as well. A generic approach allowing to put any object with 
boxes specialized seems like a better approach to me.

About geometry, I think there should be more basic objects.
While it is true polygons and multipolygons (polyhedrons) are enough to 
represent everything in 3D space, having rays, segments, triangles, 
quads, circles, spheres, squares, rectangles, cubes, cuboids (boxes), 
planes, half-planes and more, with ability to compute all intersections 
and distances, would be the most practical thing for 3D development.
I do not know how to organize this in a really dimension-agnostic 
manner, however.

In a nutshell, I think the spatial indexes design and how geometry can 
help it ought to be discussed.