Package net.imglib2.kdtree

Class KDTreeImpl

  • public class KDTreeImpl
extends java.lang.Object
    Represents the tree structure, and provides access to node coordinates (but not values).

    The nodes in the tree are arranged in Eytzinger layout (children of i are at 2i and 2i+1). Additionally, pivot indices are chosen such that "leaf layers" are filled from the left.

    For example 10 nodes will always be arranged like this: 

                0
         /     \
       1         2
     /   \     /   \
    3     4   5     6
   / \   /
  7   8 9

    never like this: 

                0
         /     \
       1         2
     /   \     /   \
    3     4   5     6
   /         /     /
  7         8     9

    By choosing pivots in this way, the tree structure is fully determined. For every node index, the child indices can be calculated without dependent reads. And iff the calculated child index is less than the number of nodes, the child exists.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int depth()  
      double getDoublePosition​(int i, int d)  
      private int ifExists​(int i)
      If a node with index i exists, returns i.
      int left​(int i)
      Get the left child of node i.
      int numDimensions()  
      int parent​(int i)
      Get the parent of node i.
      int right​(int i)
      Get the right child of node i.
      int root()
      Get the root node of the tree.
      int size()  
      int splitDimension​(int i)
      Get the dimension along which node i divides the space.
      double squDistance​(int i, double[] pos)
      Compute the squared distance from node i to pos.
      float squDistance​(int i, float[] pos)
      Compute the squared distance from node i to pos.
      double squDistance​(int i, RealLocalizable pos)
      Compute the squared distance from node i to pos.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • numDimensions

        private final int numDimensions

      • numPoints

        private final int numPoints

    • Method Detail

      • root

        public int root()
        Get the root node of the tree.
        Returns:
        index of the root node

      • left

        public int left​(int i)
        Get the left child of node i.
        Parameters:
        i - node index
        Returns:
        index of left child or -1 if no left child exists

      • right

        public int right​(int i)
        Get the right child of node i.
        Parameters:
        i - node index
        Returns:
        index of right child or -1 if no right child exists

      • parent

        public int parent​(int i)
        Get the parent of node i.
        Parameters:
        i - node index
        Returns:
        index of parent

      • ifExists

        private int ifExists​(int i)
        If a node with index i exists, returns i. Otherwise, returns -1.

      • splitDimension

        public int splitDimension​(int i)
        Get the dimension along which node i divides the space.
        Parameters:
        i - node index
        Returns:
        splitting dimension.

      • getDoublePosition

        public double getDoublePosition​(int i,
                                int d)

      • squDistance

        public float squDistance​(int i,
                         float[] pos)
        Compute the squared distance from node i to pos.

      • squDistance

        public double squDistance​(int i,
                          double[] pos)
        Compute the squared distance from node i to pos.

      • squDistance

        public double squDistance​(int i,
                          RealLocalizable pos)
        Compute the squared distance from node i to pos.

      • numDimensions

        public int numDimensions()

      • size

        public int size()

      • depth

        public int depth()