Re: [boost] Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?

Subject: Re: [boost] Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?
From: Sylvain Bougerel (sylvain.bougerel.devel_at_[hidden])
Date: 2012-04-26 21:08:12

On Mar 9, 2012 6:14 AM, "Dan Walters" <dan683@
<dan683_at_[hidden]>gmail.com<dan683_at_[hidden]>>
wrote:
>
> Hi all,
>
> I am proposing adding spacial containers for efficiently storing and
> accessing data of a spacial nature in fixed size trees.
>

Hi all,

This thread is long over, but I've been meaning to write something on it
for so long.

I wrote a kd-tree library for generic purpose. It may not sound like much,
but this library has (i believe) truly unique features : first of all,
erasing really works in amortized time (on most libraries out there it does
not -- and that's when they even propose erasing), secondly the kd-tree is
the only one i know that is capable of self-balancing.

These 2 features combined with the fact that the library is very template
based, and support any number of dimensions (that can even be determined at
runtime) makes it really a general purpose library.

It as nearest neighbor iterators, region (or bisection) iterators, and a
not so common but useful operation: a mapping iterator which maps all n
dimensions into 1 effectively making the iterator behave as a usual
multiset iterator, on 1 particular chosen dimension.

My future goal is to one day feel satisfied enough by the maturity of the
library to submit the library to Boost for integration. Sadly i haven't
reached that stage yet.

For those who are interested to try it out, you can pull the origin/master
branch from the library (the release package is stable but the code is a
bit old now) . It had burgeoning (and therefore incomplete) documentation
with some obvious mistakes.

http://spatial.sourceforge.net/

And I'm still regularly modifying the interface so it is far from being
mature. But one day... It will.

Cheers,
Sylvain