Package net.imglib2

Class KDTree<T>

java.lang.Object
net.imglib2.KDTree<T>
Type Parameters:
T - type of values stored in the tree.
All Implemented Interfaces:
Iterable<T>, EuclideanSpace, IterableRealInterval<T>, RealInterval
public class KDTree<T> extends Object implements EuclideanSpace, IterableRealInterval<T>
KDTree to access values at RealLocalizable positions.
Author:
Tobias Pietzsch

  • Field Details

    • n

      protected final int n
      the number of dimensions.

    • root

      protected final KDTreeNode<T> root

    • size

      protected final long size
      the number of nodes in the tree.

    • min

      protected final double[] min
      minimum of each dimension.

    • max

      protected final double[] max
      maximum of each dimension.

  • Constructor Details

    • KDTree

      public KDTree(List<T> values, List<L> positions)
      Construct a KDTree from the elements in the given list.

      Note that the constructor can be called with the same list for both values == positions if T extends RealLocalizable.

      Parameters:
      values - a list of values
      positions - a list of positions corresponding to the values

    • KDTree

      public KDTree(IterableRealInterval<T> interval)
      Construct a KDTree from the elements of the given IterableRealInterval.
      Parameters:
      interval - elements in the tree are obtained by iterating this

  • Method Details

    • verifyDimensions

      protected static <L extends RealLocalizable> boolean verifyDimensions(List<L> positions, int n)
      Check whether all positions in the positions list have dimension n.
      Returns:
      true, if all positions have dimension n.

    • makeNode

      protected <L extends RealLocalizable> KDTree.ValueNode<T> makeNode(List<L> positions, int i, int j, int d, List<T> values, int[] permutation)
      Construct the tree by recursively adding nodes. The sublist of positions between indices i and j (inclusive) is split at the median element with respect to coordinates in the given dimension d. The median becomes the new node which is returned. The left and right partitions of the sublist are processed recursively and form the left and right subtrees of the node.
      Parameters:
      positions - list of positions
      i - start index of sublist to process
      j - end index of sublist to process
      d - dimension along which to split the sublist
      values - list of values corresponding to permuted positions
      permutation - the index of the values element at index k is permutation[k]
      Returns:
      a new node containing the subtree of the given sublist of positions.

    • makeNode

      protected <L extends RealLocalizable> KDTree.ValueNode<T> makeNode(ListIterator<L> first, ListIterator<L> last, int d, List<T> values, int[] permutation)
      Construct the tree by recursively adding nodes. The sublist of positions between iterators first and last is split at the median element with respect to coordinates in the given dimension d. The median becomes the new node which is returned. The left and right partitions of the sublist are processed recursively and form the left and right subtrees of the node.
      Parameters:
      first - first element of the sublist of positions
      last - last element of the sublist of positions
      d - dimension along which to split the sublist
      values - list of values corresponding to permuted positions
      permutation - the index of the values element at index k is permutation[k]
      Returns:
      a new node containing the subtree of the given sublist of positions.

    • makeNode

      protected <L extends RealLocalizable> KDTree.ValueNode<T> makeNode(List<L> elements, int i, int j, int d)
      See makeNode(List, int, int, int, List, int[]). Here, no values are attached to the nodes (or rather the positions are the values).
      Parameters:
      elements - list of elements (positions and values at the same time)
      i - start index of sublist to process
      j - end index of sublist to process
      d - dimension along which to split the sublist

    • makeNode

      protected <L extends RealLocalizable> KDTree.ValueNode<T> makeNode(ListIterator<L> first, ListIterator<L> last, int d)
      See makeNode(ListIterator, ListIterator, int, List, int[]). Here, no values are attached to the nodes (or rather the positions are the values).
      Parameters:
      first - first element of the sublist to process
      last - last element of the sublist to process
      d - dimension along which to split the sublist

    • makeSamplerNode

      protected KDTree.SamplerNode<T> makeSamplerNode(List<RealCursor<T>> elements, int i, int j, int d)
      Construct the tree by recursively adding nodes. The sublist of elements between indices i and j (inclusive) is split at the median element with respect to coordinates in the given dimension d. The median becomes the new node which is returned. The left and right partitions of the sublist are processed recursively and form the left and right subtrees of the node. (The elements of the list are RealCursors which provide coordinates and values.)
      Parameters:
      elements - list of elements (positions and values at the same time)
      i - start index of sublist to process
      j - end index of sublist to process
      d - dimension along which to split the sublist
      Returns:
      a new node containing the subtree of the given sublist of elements

    • getRoot

      public KDTreeNode<T> getRoot()
      Get the root node.
      Returns:
      the root node.

    • numDimensions

      public int numDimensions()
      Description copied from interface: EuclideanSpace
      Gets the space's number of dimensions.
      Specified by:
      numDimensions in interface EuclideanSpace

    • toString

      public String toString(KDTreeNode<T> left, String indent)

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • realMin

      public double realMin(int d)
      Description copied from interface: RealInterval
      Get the minimum in dimension d.
      Specified by:
      realMin in interface RealInterval
      Parameters:
      d - dimension
      Returns:
      minimum in dimension d.

    • realMin

      public void realMin(double[] m)
      Description copied from interface: RealInterval
      Write the minimum of each dimension into double[].
      Specified by:
      realMin in interface RealInterval
      Parameters:
      m -

    • realMin

      public void realMin(RealPositionable m)
      Description copied from interface: RealInterval
      Sets a RealPositionable to the minimum of this Interval
      Specified by:
      realMin in interface RealInterval
      Parameters:
      m -

    • realMax

      public double realMax(int d)
      Description copied from interface: RealInterval
      Get the maximum in dimension d.
      Specified by:
      realMax in interface RealInterval
      Parameters:
      d - dimension
      Returns:
      maximum in dimension d.

    • realMax

      public void realMax(double[] m)
      Description copied from interface: RealInterval
      Write the maximum of each dimension into double[].
      Specified by:
      realMax in interface RealInterval
      Parameters:
      m -

    • realMax

      public void realMax(RealPositionable m)
      Description copied from interface: RealInterval
      Sets a RealPositionable to the maximum of this Interval
      Specified by:
      realMax in interface RealInterval
      Parameters:
      m -

    • size

      public long size()
      Description copied from interface: IterableRealInterval

      Returns the number of elements in this Function.

      Specified by:
      size in interface IterableRealInterval<T>
      Returns:
      number of elements

    • iterationOrder

      public Object iterationOrder()
      Description copied from interface: IterableRealInterval
      Returns the iteration order of this IterableRealInterval. If the returned object equals (Object.equals(Object)) the iteration order of another IterableRealInterval f then they can be copied by synchronous iteration. That is, having an Iterator on this and another Iterator on f, moving both in synchrony will point both of them to corresponding locations in their source domain. In other words, this and f have the same iteration order and means and the same number of elements.
      Specified by:
      iterationOrder in interface IterableRealInterval<T>
      Returns:
      the iteration order of this IterableRealInterval.
      See Also:

    • iterator

      public KDTree<T>.KDTreeCursor iterator()
      Specified by:
      iterator in interface Iterable<T>

    • cursor

      public KDTree<T>.KDTreeCursor cursor()
      Description copied from interface: IterableRealInterval

      Returns a RealCursor that iterates with optimal speed without calculating the location at each iteration step. Localization is performed on demand.

      Use this where localization is required rarely/ not for each iteration.

      Specified by:
      cursor in interface IterableRealInterval<T>
      Returns:
      fast iterating iterator

    • localizingCursor

      public KDTree<T>.KDTreeCursor localizingCursor()
      Description copied from interface: IterableRealInterval

      Returns a RealLocalizable Iterator that calculates its location at each iteration step. That is, localization is performed with optimal speed.

      Use this where localization is required often/ for each iteration.

      Specified by:
      localizingCursor in interface IterableRealInterval<T>
      Returns:
      fast localizing iterator

    • firstElement

      public T firstElement()
      Description copied from interface: IterableRealInterval
      Get the first element of this IterableRealInterval. This is a shortcut for cursor().next(). This can be used to create a new variable of type T using firstElement().createVariable(), which is useful in generic methods to store temporary results, e.g., a running sum over pixels in the IterableRealInterval.
      Specified by:
      firstElement in interface IterableRealInterval<T>
      Returns:
      the first element in iteration order.