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: Karsten Ahnert (karsten.ahnert_at_[hidden])
Date: 2012-03-09 12:16:04

I think this is a very good idea.

What about other kinds of spatial containers like r-trees or kd-trees?
How would you represent the objects within the tree? Are they points,
boxes, arbitrary geometric objects? Does the container play well with
existing geometry libraries, like boost.geometry?

On 03/08/2012 11:13 PM, Dan Walters wrote:
> 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
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost