Boost logo

Boost :

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

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at