Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-08-17 08:50:01

First of all I'd like to say that I've started to implement all 
structures from scratch. For now, I have kd-tree with one internal 
structure and 2 implementations (specified by passing tags to the 
kd-tree template).

In the attachment there are:
runtime_point.cpp - geometry::point concept wrapper providing runtime 
get(index) and set(index, value) methods used in one of the algorithms,
box.cpp - geometry::box algorithms
kd-tree.cpp - kd-tree implementation, there should be another tag used, 
indicating type of objects (in this case point_tag).

What do you think?

Before I go further I'd like to talk about the interface because I think 
that all data structures should have the same.

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

Alternatively it could be a pointer/iterator. Btw, do you write about 
internals or the interface too? I'd like to avoid returning IDs to the 
user. I'd rather use iterators and make interface similar to the one in 
std containers.

Do you have a container of geometries inside R-Tree or it's provided by 
the user? Is your R-Tree a container or just spacial index with IDs of 
elements in this user-defined container?

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

When I implemented it some time ago I was creating nodes by myself. In 
general kd-tree musn't be left balanced and it have 2 types of nodes - 
internal nodes and leafs. This would be the 2nd kd-tree structure in my 
code.

I have a few possible solutions in mind:

1. nodes' structure,

a) store nodes in a std::vector and inside nodes store indexes of left 
and right child,
b) store nodes in a std::list and store pointers/iterators (or maby use 
intrusive std::list),
c) create the structure by my own,

2. nodes,

a) store vectors of objects(IDs, ptrs) in all nodes - there will be 
empty containers inside the internal nodes,
b) store pointers to vectors and create them in runtime,
c) store lists of objects in all nodes - slower than vectors?,
d) implement simple container defined by 2 values e.g. pointers to the 
beginning and the end or number of elements,
e) store only internal nodes in the structure and store pointers to 
leafs inside them (vectors only in leafs),
f) use run-time polimorphism - this may be only used with 1c.

I don't know which one is the best. I'd like to avoid 1c, 2f and 
everything that requires using allocator by my own.

Memory allocation (pointers) could be implemented as 1-element std lists.

I'd rather use 1a and 2b (2e eventually but it's more complicated). 
Although, this means that there would be e.g. vector of nodes containing 
1-element lists of vectors. What do you think?

Regards,
Adam
-------------- next part --------------
A non-text attachment was scrubbed...
Name: spar.zip
Type: application/x-zip-compressed
Size: 5435 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/ggl/attachments/20100817/6aaed79b/spar.bin