Package net.imglib2.kdtree

Class KDTreeUtils.MakeTree

  • Enclosing class:
    KDTreeUtils
    private static final class KDTreeUtils.MakeTree
extends java.lang.Object

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private int[] indices
      Temporary array to keep track of elements.
      private int numDimensions  
      private int numPoints  
      private double[][] positions
      The coordinates for the ith point are stored at positions[d][k] where d is the dimension.
      private int[] tree
      Node indices in a flattened (heap-like) array.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private MakeTree​(double[][] positions)  

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void kthElement​(int i, int j, int k, int compare_d)
      Partition a sublist of Nodes by their coordinate in the specified dimension, such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      private void makeNode​(int i, int j, int d, int nodeIndex)  
      private static int pivot​(int len)
      Calculate pivot index such that the tree will be arranged in a way that "leaf layers" are filled from the left.

      • 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

      • positions

        private final double[][] positions
        The coordinates for the ith point are stored at positions[d][k] where d is the dimension.

      • indices

        private final int[] indices
        Temporary array to keep track of elements. Initialized to 0, 1, ... and then permuted when sorting the elements into a tree.

      • tree

        private final int[] tree
        Node indices in a flattened (heap-like) array. For example: the index of the root node is tree[0]. The coordinates of the root node are at positions[d][tree[0]] where d is the dimension. The children of the root node are at tree[1] and tree[2], and so on.

    • Constructor Detail

      • MakeTree

        private MakeTree​(double[][] positions)

    • Method Detail

      • pivot

        private static int pivot​(int len)
        Calculate pivot index such that the tree will be arranged in a way 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.

      • makeNode

        private void makeNode​(int i,
                      int j,
                      int d,
                      int nodeIndex)

      • kthElement

        private void kthElement​(int i,
                        int j,
                        int k,
                        int compare_d)
        Partition a sublist of Nodes by their coordinate in the specified dimension, such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of the sublist
        j - index of last element of the sublist
        k - index for k-th smallest value. i <= k <= j.
        compare_d - dimension by which to order the sublist