Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-01 18:26:00

Barend Gehrels wrote:
> Hi Adam,
>
> I will answer in fragments.
>
>> I've added test visualizing the rtree using GLUT, but only to the
>> https://svn.boost.org/svn/boost/sandbox-branches/geometry/index_080_nhch/
>> branch. To run it you'll neeed e.g. this:
>> http://www.opengl.org/resources/libraries/glut/glutdlls37beta.zip.
>
> Just had a look there.
>
> First this is quite cool! ;-)
>
> Second the BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW define makes the
> rtree a bit messy. Can you extract that somehow? I understand why it is
> there now, because it calls itself recursively, but that might be solved
> otherwise.
>
> Third, hmm, I thought it would be nice to demonstrate the combination of
> Boost.Geometry with GL as it is done with Qt
> <http://barendgehrels.blogspot.com/2011/02/qt-world-mapper-with-boostgeometry.html>
>
> Meaning to convert a Boost.Geometry point automatically to a GL-point like
>
> BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET(QPointF,double, cs::cartesian, x, y, setX, setY)
>
> But in GL no point concepts but just c-arrays are used. Bruno once
> created an adaption headerfile for them. Using them can draw a box like
> this:
>
> GLfloat ll[2], lr[2], ul[2], ur[2];
> geometry::assign_box_corners(it->first, ll, lr, ul, ur);
>
> glBegin(GL_LINE_LOOP);
> glVertex2fv(ll);
> glVertex2fv(lr);
> glVertex2fv(ur);
> glVertex2fv(ul);
> glEnd();
>
> Not exactly better but just shorter and maybe nicer. Or alternatively it
> can be used in a gl rectangle drawing routine.
>
> Would be nice for the examples too (like Qt - glut worldmapper). Anyway
> this whole point is not related to the spatial index at all so do with
> it what you like.

Solution 1.

There might be a method calling some function recursively:

void some_fun(rtree<Box>::rtree_node n) {...}

...

rtree<Box> t;
t.call_rec(some_fun);

but this isn't elegant.

------

Solution 2.

There could be a method returning Boxes for a given level.

std::vector<Box> boxes;
r.retrieve_boxes(level, std::back_inserter(boxes));

Elegant but not flexible. But, this is all what is needed.

------

Solution 3.

Rtree could have some node_iterator, e.g. rtree_preorder_const_iterator. 
The user could do what he wants with it. It could look like this:

rtree<Box> t;
BOOST_FOREACH(rtree<Box>::rtree_node n, t|preordered())
{
   if(!n->is_leaf())
   {
     std::vector<Box> boxes = n->get_boxes();
     // draw boxes
   }
   else
   {
     std::vector<Box> values = n->get_values();
     // draw values
   }
}

Other possibilities are e.g. t|postordered(), t|levelordered().

But I don't know if the spacial_index should have node iterators. Not in 
the "official" interface.

In addition

std::vector<Box> boxes = n->get_boxes();
BOOST_FOREACH(Box const& b, boxes)
...

could be implemented as

BOOST_FOREACH(Box const& b, n|boxes())
...

or something like this.

------
------

Still, since rtree is a container, values iterator should be 
implemented. We should be able to iterate over all values.

BOOST_FOREACH(Box const& b, t)
{
   // do something with b
}

However, this may be tricky for some containers where copies of the same 
values are stored in different nodes.

------

So I'll probably stay with Solution 2.

Regards,
Adam