Re: [boost] new library (space partitioning)

Subject: Re: [boost] new library (space partitioning)
From: Barend Gehrels (barend_at_[hidden])
Date: 2010-08-02 05:13:56

> First of all, I must explain myself. I walk in here and write that I'd 
> like to desing a library. I don't want you to change something. I'd 
> like to design a library which you might use if you haven't implement 
> some container by yourself. Moreover, I think it should be separate 
> from Boost.Geometry. What do you think about it? Have you any 
> objections? Maby you have some plans and want to do it by yourself?
Yes, I think that it is good to be separate, and I don't have objections.
What you said, it can be used for non-geometry as well.

And yes, we did have plans, actually we do have a spatial index based on 
R-Tree which lives as an extension within Boost.Geometry.

I don't think it inconvenient to have different (spatial) indexes, I 
think it is good. However, it would be very convenient to make the 
interfaces similar (or equal).

The interface of the current R-Tree still has to be redesigned so it is 
not too late, for us.

>
> If no, I think, it's the best to use concepts from Boost.Geometry 
> because it's an existing library. Or to use some adaptor.
Yes, I would advocate using our concepts. The point concept is not 
complicated and points are easy to implement and adapt to our concepts. 
The point you have in the library I saw last week can be adapted as well.

>
> But the most important thing is that if you want to make building of 
> arbitrary kd-tree possible boost::geometry::point should provide a 
> method returning given coordinate not in compile-time.
See also Luke's response on this. We have compile time access to select 
by coordinate index but, of course, you could add a wrapper in between 
translating from runtime to compiletime.

>
> Still, it is possible to create kd-tree using coordinates indexed in 
> compile-time and I don't know if it will be a lot worse than the other 
> possible trees. The problem may occur for volume objects.
I think it would be good.
>
> I might implement simple version of kd-tree for points using your 
> interface and show it to you if you like.
Yes, I would like that :-)
> Later I'd like to use adaptors and to implement some tree building 
> traits. Different building algorithms might use different interfaces 
> (compile-time or not).
We have for several free functions also different internal algorithms, 
which can be specified as an extra argument. We call that a strategy, 
there are concepts for different strategies (distance etc.). You might 
look if such a system would be convenient for you as well.

Regards, Barend