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

Subject: Re: [boost] Geometry and spatial indexes, my opinion
From: Patrick Mihelich (patrick.mihelich_at_[hidden])
Date: 2008-10-08 04:37:51

Hi Brandon,

Hi Mathias,
>
> I just wanted to say something here about dimensional agnosticism. I don't
> think this is necessarily the way to go. There are a couple of reasons that
> I say this. The more trivial point is that higher than 3D geometry isn't
> likely to be supported and isn't of much practical use anyway.

Strongly disagree! Spatial index structures are very commonly used to
accelerate nearest neighbor search, an important operation in numerous
fields. There is a nice listing at
http://en.wikipedia.org/wiki/Nearest_neighbor_search#Applications. The
search space in such applications may have hundreds of dimensions. In
computer vision we use nearest neighbor search for keypoint matching, which
in turn is fundamental to content-based image retrieval, visual odometry,
wide-baseline stereo, simultaneous localization and mapping, panorama
stitching, and the list goes on.... Computational geometry has many, many
applications beyond the obvious ones (e.g. collision detection), and
restricting yourself to 3 dimensions or fewer is rather crippling.

In my opinion, a Boost geometry library must have at least basic support for
n-dimensional computational geometry. Let's start with able to handle points
of arbitrary dimension and calculate distances between them (given some
metric). This is easy to do and already sufficient to implement many useful
spatial indices. I have not looked at Barend's geometry library in detail,
but on the surface it looks generic enough to support this.

The second point is on the basis of coordinate frameworks. While I agree
> that any library shouldn't necessarily be limited to 2D, I don't think that
> you should lose the notions of what type of coordinate frame you are working
> in. So while you may be able to have 0, 1, or 2 to describe agnostically the
> dimension in the framework you want, the descriptions of what those
> dimensions are is lost. For example, you may have an algorithm which is
> designed to work in Cartesian coordinates in 2D (or 3D). You may have
> another algorithm which requires points in Polar (Spherical) coordinates.
> Another might want cylindrical coordinates to be optimal. Then there are
> algorithms which require translation of points into parametric coordinates
> to perform some logic optimally. If you have points which are agnostic to
> dimension, how can you distinguish 0,1,2 from x,y,z or r, theta, phi?

Surely this can be handled by the type system? Simply have distinct Point3D
(Cartesian), SphericalPoint3D and CylindricalPoint3D classes with
appropriate functionality. In the vision library I used to work with, there
was a similar problem of supporting images with different numbers of
channels and different color representations (RGB, HSV, XYZ...). We
implemented them as distinct pixel types (IIRC Boost.GIL has more or less
the same architecture), and even gave them conversion operators to each
other so that we could use them interchangeably with correct behavior.

> The constraints imposed by these concepts are rather that when given a
> point of some dimensionality you need to be able to determine the type of
> coordinate frame that the point is describing. I've been working on a
> generative geometry library which includes support for these distinctions
> via conceptually enforced interfaces and traits.

So it sounds like you are already doing something of the sort?

Back to Mathias' criticisms - although I realize it is an alpha, I was
similarly a bit disappointed when looking at the Spatial Indexes library. It
is good code (I hope that Federico will not be discouraged by criticism!),
but it is very limited in what it can do currently. It has no nearest
neighbor search, nor even a traversal interface that would allow the user to
implement it himself. It only provides 2D structures when it is very useful
to support spaces of arbitrary dimension. I would like for the library to be
generic in the dimension, not just the (2D) point type. Perhaps a good place
to start is the quadtree - I do not see why the difference between a
quadtree and an octree should be more than an int template parameter.

I'm admittedly opening up a bit of a can of worms here - nearest neighbor
search in high dimensions is a Hard Problem. However, there are
straightforward approximate nearest neighbor algorithms that are efficient
and plenty good enough for many applications.

Let me summarize with a wish list:
  * tree traversal interface
  * generic in the dimension for any structure for which this makes sense
  * (k-)nearest neighbor and other standard query methods, as mentioned by
Mathias
  * kd-tree implementation
  * metric tree implementation (splits need not be axis-aligned)
  * one or more good bulk-loading algorithms for each structure (repeated
insertion is not acceptable)
  * approximate (k-)nearest neighbor search

I could add some more items, but this is already a daunting amount of work.
So perhaps Federico and Barend can clarify, what are their plans for
development of the Spatial Index library? Do they include any of the items
above? It seems to me that Federico's work is quite a good start, but there
is a great deal of room for future development.

Cheers,
Patrick