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.