Class KDTreeImpl

java.lang.Object
net.imglib2.kdtree.KDTreeImpl
public class KDTreeImpl extends 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.

  • Field Details

    • numDimensions

      private final int numDimensions

    • numPoints

      private final int numPoints

    • positions

      private final KDTreePositions positions

  • Constructor Details

  • Method Details

    • 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()