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