Package gov.nih.mipav.model.algorithms

Class KDTree

java.lang.Object
gov.nih.mipav.model.algorithms.KDTree
public class KDTree extends Object
Original code Copyright (C) 2007-2011 John Tsiombikas invalid input: '<'nuclear@member.fsf.org> 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 invalid input: '<'nuclear@member.fsf.org> 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 Details

  • Constructor Details

    • KDTree

      public KDTree()

  • Method Details

    • test

      public void test()

    • test2

      public void test2()

    • dist_sq

      public double dist_sq(double[] a1, double[] a2, int dims)

    • rd

      public double rd(Random rnd)

    • SQ

      public double SQ(double x)

    • kd_create

      public KDTree.kdtree kd_create(int k)

    • kd_free

      public void kd_free(KDTree.kdtree tree)

    • kd_clear

      public void kd_clear(KDTree.kdtree tree)

    • clear_rec

      public static void clear_rec(KDTree.kdnode node)

    • insert_rec

      public int insert_rec(KDTree.kdnode nptr, boolean nptrwasnull, double[] pos, double[] data, int dir, int dim)

    • kd_insert

      public int kd_insert(KDTree.kdtree tree, double[] pos, double[] data)

    • kd_insertf

      public int kd_insertf(KDTree.kdtree tree, double[] pos, double[] data)

    • kd_insert3

      public int kd_insert3(KDTree.kdtree tree, double x, double y, double z, double[] data)

    • kd_insert3f

      public int kd_insert3f(KDTree.kdtree tree, float x, float y, float z, double[] data)

    • find_nearest_chebyshev

      public int find_nearest_chebyshev(KDTree.kdnode node, double[] pos, double range, KDTree.res_node list, int ordered, int dim)

    • find_nearest

      public int find_nearest(KDTree.kdnode node, double[] pos, double range, KDTree.res_node list, int ordered, int dim)

    • kd_nearest_i

      public void kd_nearest_i(KDTree.kdnode node, double[] pos, KDTree.kdnode result, double[] result_dist_sq, KDTree.kdhyperrect rect)

    • kd_nearest

      public KDTree.kdres kd_nearest(KDTree.kdtree kd, double[] pos)

    • kd_nearestf

      public KDTree.kdres kd_nearestf(KDTree.kdtree tree, float[] pos)

    • kd_nearest3

      public KDTree.kdres kd_nearest3(KDTree.kdtree tree, double x, double y, double z)

    • kd_nearest3f

      public KDTree.kdres kd_nearest3f(KDTree.kdtree tree, float x, float y, float z)

    • kd_nearest_range

      public KDTree.kdres kd_nearest_range(KDTree.kdtree kd, double[] pos, double range)

    • kd_nearest_range_chebyshev

      public KDTree.kdres kd_nearest_range_chebyshev(KDTree.kdtree kd, double[] pos, double range)

    • kd_nearest_rangef

      public KDTree.kdres kd_nearest_rangef(KDTree.kdtree kd, float[] pos, float range)

    • kd_nearest_range3

      public KDTree.kdres kd_nearest_range3(KDTree.kdtree tree, double x, double y, double z, double range)

    • kd_nearest_range3f

      public KDTree.kdres kd_nearest_range3f(KDTree.kdtree tree, float x, float y, float z, float range)

    • kd_res_free

      public void kd_res_free(KDTree.kdres rset)

    • kd_res_size

      public int kd_res_size(KDTree.kdres set)

    • kd_res_rewind

      public void kd_res_rewind(KDTree.kdres rset)

    • kd_res_end

      public int kd_res_end(KDTree.kdres rset)

    • kd_res_next

      public int kd_res_next(KDTree.kdres rset)

    • kd_res_item

      public double[] kd_res_item(KDTree.kdres rset, double[] pos)

    • kd_res_itemf

      public double[] kd_res_itemf(KDTree.kdres rset, float[] pos)

    • kd_res_item3

      public double[] kd_res_item3(KDTree.kdres rset, double[] x, double[] y, double[] z)

    • kd_res_item3f

      public double[] kd_res_item3f(KDTree.kdres rset, float[] x, float[] y, float[] z)

    • kd_res_item_data

      public double[] kd_res_item_data(KDTree.kdres set)

    • hyperrect_create

      public KDTree.kdhyperrect hyperrect_create(int dim, double[] min, double[] max)

    • hyperrect_free

      public static void hyperrect_free(KDTree.kdhyperrect rect)

    • hyperrect_duplicate

      public KDTree.kdhyperrect hyperrect_duplicate(KDTree.kdhyperrect rect)

    • hyperrect_extend

      public static void hyperrect_extend(KDTree.kdhyperrect rect, double[] pos)

    • hyperrect_dist_sq

      public double hyperrect_dist_sq(KDTree.kdhyperrect rect, double[] pos)

    • alloc_resnode

      public KDTree.res_node alloc_resnode()

    • free_resnode

      public void free_resnode(KDTree.res_node node)

    • rlist_insert

      public int rlist_insert(KDTree.res_node list, KDTree.kdnode item, double dist_sq)

    • clear_results

      public void clear_results(KDTree.kdres rset)