Re: [boost] new library (space partitioning)

Subject: Re: [boost] new library (space partitioning)
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2010-08-07 11:13:15

Just adding a few things to what I said:

07/08/2010 15:29, Mathias Gaunard wrote:

> What a spatial index does is fairly simple (to the user). Its interface
> should be the same as that of std::multiset, but instead of using
> operator<, it should use intersection (which, like std::multiset, should
> have a default but be changeable to an arbitrary function object).

While intersection test should be enough for searching, you're going to 
need other primitives for maintaining the data structure.
They probably should be template parameters as well.

For r-trees, for example, you're going to need a function that gives the 
axis-aligned bounding box for a T, and Geometry does provide that with 
the 'envelope' function.
But in a typical scenario, you're going to want to precompute all the 
bounding boxes for all objects before you index them, so having a 
customized function that just returns the pre-calculated envelope seems 
needed.

> You're going to want to change std::multiset<T>::find slightly to allow
> arbitrary types, not just T (often considered an arbitrary limitation
> and defect by people), and to return a range instead of an iterator; and
> you might want to lazily evaluate that range as well, hence providing
> the incremental search you put on your to-do list.

You may want to add another find function that sorts the results by 
distance as well, for nearest neighbour queries.