Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-01-29 08:17:53

In addition to the discussion about query interface I'd like to start 
new one regarding spacial index creation.

Existing rtree interface looks as follows:

rtree<Box, Value> rt(maximum_elements, minimum_elements);

rt.insert(Box(/*...*/), Value(/*...*/));
rt.insert(Box(/*...*/), Value(/*...*/));
rt.insert(Box(/*...*/), Value(/*...*/));

std::deque<Value> result = find(Box(/*...*/));

where Box is a type adapted to geometry::model::box concept and Value is 
some value connected to the Box. It may be some object's identifier or 
Box's additional data. Internally this pair is allways stored as 
std::pair<Box, Value>.

The intention of this interface is to have some external volumetric 
objects collection and to store just some ids inside spacial index. This 
is just one of possible uses.

What if someone wants to use our rtree as a primary container to store 
some kind of point objects. Existing implementation requires three 
copies of this point, internally it stores these three points and 
doubles processing e.g. in boxes expanding. It looks like this:

rtree<box<Point>, Point> rt(ma, mi);
rt.insert(box<Point>(Point(), Point()), Point());

What if someone implements some volumetric object class which has a box 
inside. It's very common. Boxes are doubled.

I'd like to propose slightly different implementation. The main idea is 
to provide a translator object which translates from Values to Box or 
Point. Our index now stores a translator and our Values. Internally 
Values are stored and algorithms for Boxes and Points are choosen in 
compile time. It would look like this:

template <typename Value, typename Translator = vtr::default<Value> >
class rtree
{
   rtree(unsigned int maximum, unsigned int minimum, Translator tr = 
vtr::default<Value>() ) : m_tr(tr)
   {
     /*...*/
   }

   void insert(Value const& v)
   {
     /*...*/
   }

   /*...*/

   private:
     Translator m_tr;
};

For Values adapted to geometry::point:

rtree<MyPoint> rt(ma, mi);
rt.insert(MyPoint());

For Values adapted to geometry::box:

rtree<MyBox> rt(ma, mi);
rt.insert(MyBox());

For some data (ID) stored with corresponding point:

rtree< std::pair<Point, Id> > rt(ma, mi);
rt.insert(std::pair<Point, Id>(Box(), Id()));

For some data (ID) stored with corresponding box:

rtree< std::pair<Box, Id> > rt(ma, mi);
rt.insert(std::pair<Box, Id>(Box(), Id()));

For a shared pointer to object of a class adapted to geometry box concept:

rtree< boost::shared_ptr<MyBox> > rt(ma, mi);
rt.insert(boost::shared_ptr<MyBox>(new MyBox()));

For some user-defined volumetric object with method get_box() 
implemented stored inside std::vector:

class MyTranslator
{
public:
   typedef box_tag tag_type;

   MyTranslator(std::vector<MyObj> const& v) : m_v(v) {}

   Box const& operator()(size_t v_index)
   {
     return m_v[v_index].get_box();
   }
private:
   std::vector<MyObj> const& m_v;
};

/*...*/

rtree<size_t, MyTranslator> rt(ma, mi, MyTranslator(my_vector));
rt.insert(0);
rt.insert(1);

What do you think?

Regards,
Adam