Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-07 13:16:47

Bruno Lalande wrote:
> Hi,
>
>
>         So std::vector< std::pair<Box, node_pointer > > was in leafs but
>         not used. Now this is implemented as follows:
>
>         [...] I've also changed some names to better describe variables.
>
>
>     Great. If a vector is not used, it should go indeed. Perfect.
>
>
> Hmm I'm not sure... This reminds me the way in which script languages
> like Python or Perl implement "pure" virtual functions by just having
> their default implementation throw an error, while compiled languages
> allow the function not to exist at all when not needed (and thus "throw"
> at compile time).
>
> This function should not even be virtual. Leaf and Node should have
> there own set of (non virtual) specific functions only applicable to
> them, and those functions should be called by double dispatch. With
> double dispatch, once you are in the second step of the dispatching
> process, you know (at compile time) that you are manipulating a node or
> a leaf, and you can call methods on them which are not virtual at all,
> and don't exist in the base class.
>
> And if no such specific method exist (i.e. if there's nothing you can do
> with a leaf that you can't do with a node and the other way around) then
> there should only be one class, with a container of itself, and testing
> for leaf boils down to testing that container for emptiness. But I guess
> you're not in this case?

Methods are implemented in a way they were implemented in the original. 
I've just changed the hierarchy since there were already virtual methods 
and one container wasn't used.

We must distinguish between leafs and nodes in run time so we must have 
virtual functions or condition and type casts.

I can imagine these possible implementations:

1. Full run-time polimorphism.

Close to the existing implementation.

class node
{
   virtual void some_method() = 0;

   node_ptr parent;
};

class internal_node : node
{
   virtual void some_method() {...}

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

class leaf : node
{
   virtual void some_method() {...}

   std::vector<Value> m_values;
};

class rtree
{
   ...
   void do_something()
   {
     node_ptr n = init_ptr();
     n->some_method();
   }
   ...
};

2. One virtual function is_leaf()

class node
{
   virtual bool is_leaf() = 0;

   node_ptr parent;
};

class internal_node : node
{
   virtual is_leaf() { return false; }

   void some_method() {}

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

class leaf : node
{
   virtual is_leaf() { return true; }

   void some_leaf_method() {...}

   std::vector<Value> m_values;
};

class rtree
{
   ...
   void do_something()
   {
     node_ptr n = init_ptr();
     if ( n->is_leaf() )
       static_cast<leaf*>(n)->some_leaf_method();
     else
       static_cast<internal_node*>(n)->some_method();
   }
   ...
};

3. No virtuals. Unused data.

class node
{
   bool is_leaf() { return m_nodes.empty(); }

   void some_method()
   {
     if ( is_leaf() )
       // do something
     else
       // do something else
   }

   void other_leaf_method()
   {
     if ( is_leaf() )
       // do something
     else
       assert(SOMETHING);
   }

   node_ptr parent;
   std::vector<std::pair<Box, node_ptr> > m_nodes;
   std::vector<Value> m_values;
};

class rtree
{
   ...
   void do_something()
   {
     node_ptr n = init_ptr();
     n->some_method();

     ...

     std::vector<node_ptr> leafs;
     BOOST_FOREACH(node_ptr leaf, leafs)
       leaf->other_leaf_method();
   }
   ...
};

I'm open to suggestions.

>         1. Bruno mentioned that he has an idea for a slightly different
>         translator.
>
>
> Well I've thought a bit about that and I don't think I can come up with
> anything much better. If I summarize, the translator is basically just a
> function (which takes an index and returns the corresponding indexable)
> so maybe we should call it Translate or GetIndexable or something like
> that to state that more clearly. And more important, we should ensure a
> boost::function or any Boost or STL binder can be used. Does that make
> sense? Basically, I'd like to somehow state more clearly that this is
> just a function/functor.

At the beginning it was jus a functor but later I realized that there 
should be equals() function. For other spatial indexes there will 
probably be other methods doing different things. Default 'translator' 
will have some number of methods used by different spatial indexes. So 
maby implementing it as a functor isn't the best idea. This is something 
like run-time traits. The name should probably refer to the 'index' or 
'indexing'.

>         geometry::index::remove(spatial_index, value);
>         geometry::index::remove(spatial_index, value_first, value_last);
>         geometry::index::remove_from(spatial_index, box);
>
>
>     Yes, this is symmetric to insert. I don't know if a box is often
>     used for removal, intuitively I would remove everything outside a
>     box, to concentrate on that area.
>
>
> By removing from a box, do you mean removing all the data which is in
> the box represented by one of the nodes/leaves of the tree? Or removing
> all data which is geometrically contained by an arbitrary box? In the
> first case, I don't think it makes sense (the user is not even supposed
> to be aware of the internally structure, so not supposed to be
> interested in basing some removal upon an element of the structure). In
> the second case, it might make sense to have such function.

This function should remove every object inside some box but as I've 
written before it is only an example.

Two functions which are needed for sure are insert(index, value) and 
remove(index, value). The rest is optional but certainly could be 
useful. I'm talking about how the interface should look like for now.

Regards,
Adam