Boost logo

Geometry :

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)


     Translator m_tr;

For Values adapted to geometry::point:

rtree<MyPoint> rt(ma, mi);

For Values adapted to geometry::box:

rtree<MyBox> rt(ma, mi);

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
   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();
   std::vector<MyObj> const& m_v;


rtree<size_t, MyTranslator> rt(ma, mi, MyTranslator(my_vector));

What do you think?


Geometry list run by mateusz at