Boost logo

Boost :

Subject: [boost] Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?
From: Dan Walters (dan683_at_[hidden])
Date: 2012-03-08 17:13:56


Hi all,

I am proposing adding spacial containers for efficiently storing and
accessing data of a spacial nature in fixed size trees.

n-tree data structures would be useful where data relates to a 1D, 2D or 3D
location, providing n-array searching of an n-array volume. N-tree data
structures are commonly used in 3d applications, and are rarely
particularly specialized. Their use is fundamental however they are
frequently written by application programmers, due to a lack of free open
source implementations (to the limit of my research). Their sophistication,
like any container, is slim but easy to get wrong and beyond the ability
and time contraints that should be assumed of the application programmer.
It is a flexible and standard enough concept that a single implementation
can be expected to meet a majority of requirements. I think there is the
opportunity to create a solid implementation of templated n-tree pointer
containers.

The ntree container would be a tree representing an narray of elements with
all dimensions being the same and being a power of two. The tree is memory
efficient where areas within the volume are not occupied, and so "branches"
and "leaves" are not created. The tree is well suited to geometrical
operations such as ray picking or plane culling of the volume. An n-tree
structure could be used in the place of any sparely populated n dimensional
array where memory saving is the objective.

The existing libraries I have found are licensed under GNU licenses.

A ntree container should implement:

get
reset
overloaded (array style) operators

Optional implementations:

views - a subset object representing an area or volume within the tree for
accelerated access to a group of leaves that are positioned near to each
other

raycasting
plane culling (getting leaves within a set of planes)
etc.

Is there interest in such a library?

Many thanks,

Dan


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk