Re: [boost] Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?
Hi all, This is my current implementation of an oct tree that I am using on a project I am working on. It is a templated oct tree which serves as a pointer container. There is usage shown in the main() function at the bottom of the sample. http://codepad.org/yIAblSDN Please bear in mind it is not fully optimized or std compliant, just put together for a project but shows the intended basic functionality and method. Compatibility with boost geometry is a great suggestion. Again, I am mindful of defining the boundaries of this library, but if it makes sense then template specialization or utility code could be provided to use the libraries together easily and elegantly. k-d trees are very interesting, and if discussion found these potentially useful enough, they would certainly belong in the same library. I think, in any context, this should be thought of as a container library above all else and would be potentially useful not just in game or geometry programming, but open to use where ever useful, including as a memory efficient pointer container for sparsely populated multidimensional arrays. Best wishes, Dan On 10 March 2012 20:04, Daniel F. Savarese <dfs@savarese.org> wrote:
In message <848178090.20120310163009@gmail.com>, pavel writes:
by the way i have a ready implementation of kd trees (if anyone is interested):
http://programmizm.sourceforge.net/blog/2011/a-practical-implementation-of-k...
trees
That's not exactly a generic implementation, nor one that is STL-friendly (e.g., no iterators). For a more generic implementation that aims for STL interoperability where possible, see the header-only libssrckdtree library: http://www.savarese.com/software/libssrckdtree/
But this is off-topic for the thread, which--as I understand it--is concerned with fixed-size multidimensional spatial pointer containers oriented toward 3D applications, not variable-sized multidimensional spatial value containers applicable to arbitrary domains.
daniel
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Dan Walters wrote:
Hi all,
This is my current implementation of an oct tree that I am using on a project I am working on. It is a templated oct tree which serves as a pointer container. There is usage shown in the main() function at the bottom of the sample.
Please bear in mind it is not fully optimized or std compliant, just put together for a project but shows the intended basic functionality and method.
Compatibility with boost geometry is a great suggestion. Again, I am mindful of defining the boundaries of this library, but if it makes sense then template specialization or utility code could be provided to use the libraries together easily and elegantly.
k-d trees are very interesting, and if discussion found these potentially useful enough, they would certainly belong in the same library.
I think, in any context, this should be thought of as a container library above all else and would be potentially useful not just in game or geometry programming, but open to use where ever useful, including as a memory efficient pointer container for sparsely populated multidimensional arrays.
Hi, Some time ago I had the same idea. To keep it short - I wasn't the first one. As far as I know there were a lot of arguing on the list about it and the community agreed that these types of structures should be a part of Boost.Geometry. I have in mind spatial indexes/space partitioning structures. Maby you don't know but there is already an implementation of a R-tree in the extensions of Boost.Geometry and the new version, implemented by me in the https://svn.boost.org/svn/boost/sandbox-branches/geometry/index/. Have you implemented fully functional spatial index or a base data structure (a tree of arrays) which may be at the bottom of e.g. an octree? I think it's a good idea to start with the Boost.Geometry mailing list. Regards, Adam
participants (2)
-
Adam Wulkiewicz -
Dan Walters