Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Barend Gehrels (barend)
Date: 2011-03-06 12:52:23

Hi Adam,

> Previously it looks like this:  [...]
>
> 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.

One of the things I've remarked in the past (> year ago) is: can we 
avoid virtual functions here? The spatial index as implemented was 
reported as slower than usual, or possible, don't know the details. If 
you're now diving into this, can you see if there are improvements possible?

In the currently running xint review the CRTP is proposed instead of 
virtual functions, and it might be that this is also possible here. If 
so, that is probably preferable.

>
>>>
>>>> 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.

Is it true that the translator falls between a traits class and a 
policy? It is definitely a bit like a traits class, and you noticed that 
it must be possible to use two different translators for one structure. 
We have similar things in Boost.Geometry. In some cases you can specify 
a policy. In other cases we call it a strategy, that is in the context 
of Boost.Geometry explicitly used to implement behaviour dependant on 
coordinate systems. But in fact, it is a sort of policy. And it is 
specified at runtime, but there is a default defined at compile time. I 
think this is similar to what you want with the translator. But there it 
is attached to the spatial index.

> 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);

I think this is a very good idea and similar to how Boost.Geometry is. I 
didn't think earlier to apply this for spatial indexes, but I think it 
is a good idea.

What is exactly value_first, value_last? Do you mean iterators here?

>
> 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);

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.

Is index::remove_if(spatial_index, condition_functor);

an idea? You can build a functor then and specify a box, and if removal 
should be inside or outside.

>
> 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?

Ah, this is probably similar to what I justed typed a few lines above 
;-) So remove_if?

Regards, Barend

-- 
Barend Gehrels
http://about.me/barendgehrels