Geometry Boost List: [ggl] space partitioning

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
-------------------------------------
http://www.erplex.com
http://trac.osgeo.org/ggl
http://www.geodan.nl
-------------------------------------
Geodan
President Kennedylaan 1
1079 MB Amsterdam
The Netherlands
-------------------------------------
Tel: [phone]
Mob: [phone]
Fax: [phone]
-------------------------------------
E-mail: barend.gehrels_at_[hidden]
Kvk-nummer: 33 207089
Disclaimer: www.geodan.nl/disclaimer
-------------------------------------