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

Subject: Re: [boost] Geometry and spatial indexes, my opinion
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2008-10-08 10:51:05

Hi Patrick,

:)
--------------------------------------------------
From: "Patrick Mihelich" <patrick.mihelich_at_[hidden]>
Sent: Wednesday, October 08, 2008 3:37 AM
To: <boost_at_[hidden]>
Subject: Re: [boost] Geometry and spatial indexes, my opinion

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

Ok, I take your point. I wasn't suggesting that a library not be able to 
handle more than 3 dimensions. Rather I would suggest that the population of 
developers who have such requirements must be very small. Considering that 
generalization on dimension is not trivial for many algorithms, this leads 
me to the conclusion that the specific algorithms will decide the 
requirements on their inputs. This is why I chose a traits based interface 
for the geometry library I've been implementing. There's nothing to stop one 
from creating a multi-dimensional Cartesian/polar/parametric access traits 
interface for any algorithm which requires it. So I suppose I agree, the 
geometry library should not constrain on the number of dimensions. But I 
don't agree with full agnosticism (to mean agnosticism of coordinate frame 
as well.) There should be a way to differentiate points further to align 
with the concrete traits of the dimension they describe.

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

One certainly could if they chose to take the route of providing all these 
point classes.

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

Yes, I have taken a slightly different route than the other libs I have 
found in the vault. In my library the algorithms require inputs conform to a 
specific access traits concept. I have been using get_x, get_y, get_z as the 
general interface for cartesian (and would have used get_r, get_theta, 
get_phi for the others.. if I had gotten to that), but I think now that I'm 
fairly well persuaded to investigate a compile time indexed mechanism like 
boost::tuple. Has anyone done a performance test on using such a mechanism 
in practical settings? While I'm sure it's constant, how big is that 
constant in practice? Is it worth paying in cases where an algorithm 
requires a constrained dimensionality? I'm guessing nobody has really 
addressed these questions... so perhaps I'll take a gander and see if it's 
worth providing both interfaces in my access traits.

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

I can't say that I have seriously considered this. Just out of curiosity, 
how do kd-trees scale memory-wise on average in high dimension?

> 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

Cheers,

Brandon

> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>