Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Barend Gehrels (barend.gehrels)
Date: 2010-08-16 09:13:17

Hi Adam,

> My name is Adam Wulkiewicz and I'd like to take a part in GGL 
> evolution by implement space partitioning data structures. Those who 
> are subscribers of Boost mailing list know the situation. I've moved 
> the discusion from there.

Welcome to this list!

As expressed on the Boost List, space partitioning is welcome within
Boost.Geometry (GGL)

>
> I think it's possible that we misunderstood each other. I'll clarify.

Thanks for your clarification. Yes, the center point is clear to me: the
std::vector is on the stack and it allocates dynamic memory itself.
Maybe I didn't express myself well enough, I said: "do not allocate
dynamic memory ourselves;" and I meant: we don't do it, but it is done
by the std container. So indeed, the memory itself is on the heap, sure.
No problem for me.

>
> The simplest form of tree's nodes structure will be a std::vector 
> (like in the heap). For point kd-tree we may have nodes which are our 
> points, possibly with some kind of additional data. But for volumetric 
> objects, nodes must specify splitting planes positions and we must 
> store a conteiner of objects in each leaf node (e.g. std::vector). In 
> both cases memory is allocated on the heap e.g. by std::allocator. 
> Btw, in the second example we end up with half of tree nodes 
> containing empty vectors because objects are stored in leafs so 
> different internal structure should be used.
One additional question: I assume you don't make copies of the objects
there? So just references? How does that work?

In the R-Tree implementation which is already there, all objects are
referred to an ID (a template parameter, usually an int) and you get
ID-s back. This works quite well and avoids creating copies of (often
large) geometries. How will that work in your design?

>
> In the first article we have an algorithm creating kd-tree for 
> volumetric objects using Surface Area Heuristic. The container 
> (std::vector) of split candidates is generated at the beginning of 
> building process, sorted and passed to the recursive build function. 
> It's possible that on each recursive step some objects will overlap 
> the splitting plane. New bounds on both sided of the plane are 
> calculated and new split candidates are generated (std::vector), 
> sorted and merged with split candidates for each node. In addition, we 
> must pass proper objects to the left and right child nodes so we have 
> to create std::vectors of children nodes' objects each time or use one 
> container created at the beginning (just like for split candidates) 
> insert newly created objects (copies of objects overlapping the 
> splitting plane) and rearrange the ranges of this container in order 
> to pass iterators defining those ranges. These all std::vector objects 
> are created on the stack but memory is allocated on the heap.

Thanks, I didn't read the article yet... Do you have a vector of
vectors? Is the vector the best candidate (what about a list - or it is
configurable anyway).

>
> And (as far as I know) there is not possible to dynamically allocate 
> memory on the stack. There might be some kind of fixed-size container 
> (e.g. boost::array) and std::vector used if number of objects exceeds 
> this fixed-size container's size. There might be some kind of 
> allocator which does it. But I don't know if this is what you had in 
> mind. 
No, certainly not, see above.

> If you thought of that temporary containers objects should be created 
> on the stack in the building process there is no problem, but the 
> memory will still be allocated on the heap.
No problem for me, I think it should be there indeed.
>
> And yes, all of these containers and allocators may be specified by 
> the user.

Sounds good.

Regards, Barend