Boost logo

Boost :

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

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

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