Boost logo

Geometry :

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

Hi Adam,

Thanks for your quick implementation!

I didn't look at it yet but will do soon. So here reaction on your text:

>> 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.
O yes, sure, sorry. The current rtree interface returns a deque of ID's.
That is not what we wanted. An interface with iterators and similar to
containers is much better. We (internally) discussed this before.

However, I here meant the ID instead of the object itself. I think that
is OK.

It will be a challenge to get the interface exactly right.

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

No, the geometrires are not stored inside the RTree, just the boxes. So
it is a spatial index with ID's of elements.

>> 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'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?
I have to study this in more detail.

Regards, Barend

Barend Gehrels
President Kennedylaan 1
1079 MB Amsterdam
The Netherlands
Tel: +31 (0)20 5711 335
Mob: +31 (0)6 175 447 62
Fax: +31 (0)20 5711 333
E-mail: barend.gehrels_at_[hidden]
Kvk-nummer: 33 207089

Geometry list run by mateusz at