Boost logo

Boost :

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


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
     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
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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at