Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-05 15:47:53

Barend Gehrels wrote:
> Hi Adam,
>
>> I'm working on
>> https://svn.boost.org/svn/boost/sandbox-branches/geometry/index_080_nhch/
>> branch now. I've implemented different nodes hierarchy. There is
>> abstract class rtree_node and both rtree_leaf and
>> rtree_internal_node(previous rtree_node) are derived from it. I've
>> done it to avoid duplication of unused std::vector containing children
>> nodes in leafs.
>
> OK, I'm curious.

Previously it looks like this:

class rtree_node
{
public:
   virtual void do_something_with_leaf()
   {
     throw some_exception("this method should be called for leaf only");
   }

   ...

private:
   node_pointer m_parent;
   unsigned int m_level;

   std::vector< std::pair<Box, node_pointer > > m_nodes;
};

class rtree_leaf : public rtree_node
{
public:
   virtual void do_something_with_leaf()
   {
     // do something
   }

   ...

private:
   std::vector<Value> m_nodes;
};

So std::vector< std::pair<Box, node_pointer > > was in leafs but not 
used. Now this is implemented as follows:

class rtree_node
{
public:
   virtual void do_something_with_leaf()
   {
     throw some_exception("this method should be called for leaf only");
   }

   ...

private:
   node_pointer m_parent;
   unsigned int m_level;
};

class rtree_internal_node : public rtree_node
{
public:
   ...

private:
   std::vector< std::pair<Box, node_pointer > > m_nodes;
};

class rtree_leaf : public rtree_node
{
public:
   virtual void do_something_with_leaf()
   {
     // do something
   }

   ...

private:
   std::vector<Value> m_values;
};

I've also changed some names to better describe variables.

>>
>>> BTW, have you considered including boost::ref in the possible things the
>>> default translator can handle? Some users might need that, I think.
>>
>> I haven't thought about this but this is probably a good idea. I plan
>> to handle tuples as well. But I'm waiting for the clarification of the
>> interface design.
>
> Is this actually waiting for me? I thought I did react on most points.
> Which part of the interface should still be clarified?

1. Bruno mentioned that he has an idea for a slightly different translator.

2. If we have other data structures, translator will have additional 
methods. It already has equals. So it probably should have name changed.

3. The interface should provide a uniform way of use of spatial indexes 
(it may be used by boost::geometry algorihtms or users). We have well 
designed query interface. But I'm thinking about creation interface. 
Should some functionalities be implemented in all spacial indexes? E.g. 
inserting of new element. Some indexes may not have this kind of 
functionality and be build only once. For some of them it may be needed 
to call some method after adding some elements.

We should define some basic functionalities.

Then, we should separate from 'native' spatial index's interface by use 
of some functions.

Examples:

geometry::index::insert(spatial_index, value);
geometry::index::insert(spatial_index, value_first, value_last);

If functions won't be implemented for some container, default ones will 
be used. Lack of needed methods will cause compilation error.

4. There is functionality of removing elements from spatial index. User 
may want to remove exact value or all values inside some box. If value 
is a box, we have two methods remove(...) with the same parameter. 
Simplest way to avoid it is to change the name of one method. I've 
implemented remove(Value) and remove_in(Box) but maby you have better 
idea? I now realised that better name would be remove_from(Box).

Then:

geometry::index::remove(spatial_index, value);
geometry::index::remove(spatial_index, value_first, value_last);
geometry::index::remove_from(spatial_index, box);

5. All functionalities that are implemented in the rtree are: insert, 
remove and remove_from.

6. What do you think about removing elements from box but with some 
filter? Removing only some of the elements from box?

Regards,
Adam