Package gov.nih.mipav.model.algorithms

Class KDTree

  • public class KDTree
extends java.lang.Object
    Original code Copyright (C) 2007-2011 John Tsiombikas Ported to Java by William Gandler Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 3. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. kdtree ====== .. image:: http://nuclear.mutantstargoat.com/sw/kdtree/img/kdtree_logo.png Overview -------- kdtree is a simple, easy to use C library for working with kd-trees. Kd-trees are an extension of binary search trees to k-dimensional data. They facilitate very fast searching, and nearest-neighbor queries. This particular implementation is designed to be efficient and very easy to use. It is completely written in ANSI/ISO C, and thus completely cross-platform. See under the doc/ and examples/ directories to find out how to use the kdtree library. License ------- Author: John Tsiombikas kdtree is free software. You may use, modify, and redistribute it under the terms of the 3-clause BSD license. Download -------- Latest release (0.5.7): http://nuclear.mutantstargoat.com/sw/kdtree/files/kdtree-0.5.7.tar.gz You can find previous releases here: http://nuclear.mutantstargoat.com/sw/kdtree/files/ You can also grab a copy of the source from github: https://github.com/jtsiomb/kdtree Programming guide Using the kdtree library in your programs is very easy. Creating a tree Call the kd_create function to create a tree. It takes a single argument specifying the dimensionality of the data, and returns a pointer to the tree. You need to pass that pointer as an argument to any functions that manipulate the kd-tree. For example you may create a 3-dimensional kd-tree with: void *kd = kd_create(3); Destroying a tree Call kd_free with a pointer returned from kd_create in order to free the memory occupied by the tree. Note that any data pointers passed by the user with the kd_insert functions will not be freed, unless a "data destructor" function is provided (see below). Managing user pointers When inserting data to the tree, you may pass a pointer to be stored in the node. If you wish, you may provide a custom "destructor" function to be called for each of these pointers when their node is removed from the tree. You can do that by supplying a pointer to that destructor function with a call to kd_data_destructor. The first argument is again a valid pointer to a kd-tree, while the second argument is a function pointer with the signature: void (*)(void*). Populating the tree To insert data to the kd-tree you may use one of the kd_insert functions. All of the insertion functions take a valid tree pointer as their first argument, and an optional pointer to user data to be stored along with the node as their last argument (it can be null if no user data are needed). kd_insert, and kd_insertf expect a pointer to an array of k doubles or floats respectively as a second argument, which contain the position of the inserted point. So for example, for a 3D tree you need to pass an array of 3 values. The convenience kd_insert3, and kd_insert3f are meant to be called for 3-dimensional kd-trees (which is considered the most common case), and expect 3 values (doubles or floats) signifying the position of the 3-dimensional point to be stored. Performing nearest-neighbor queries After you have your data in the kd-tree, you can perform queries for discoverying nearest neighbors in a given range around an arbitrary point. The query returns a pointer to the "result set", which can from then on be accessed with the kd_res_* functions. The nearest-neighbor queries are performed with the kd_nearest_range functions. Like the kd_insert functions described above, they also provide generic array argument versions for k-dimensional trees, and 3-dimensional convenience functions, all in double and float varieties. For example in order to query for the nearest neighbors around the 2D point (10, 15), inside a radius of 3 units, you could do: void *result_set; double pt[] = {10.0, 15.0}; result_set = kd_nearest_range(kd, pt, 3.0); where "kd" is a pointer to a 2-dimensional kd-tree returned by kd_create(2). A result set aquired with one of the kd_nearest_range functions, must be freed by calling kd_res_free and supplying the result set pointer as its only argument.

    • Field Detail

      • alloc

        final java.util.concurrent.locks.Lock alloc

    • Constructor Detail

      • KDTree

        public KDTree()