KDTree (ImgLib2 Javadocs 0-SNAPSHOT API)

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

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`static class`	`KDTree.DimComparator<L extends RealLocalizable>` Compare RealLocalizables by comparing their coordinates in dimension d.
`class`	`KDTree.KDTreeCursor`
`protected static class`	`KDTree.SamplerNode<T>` A KDTreeNode that stores it's value as a Sampler.
`protected static class`	`KDTree.ValueNode<T>` A KDTreeNode that stores it's value as a reference.

Field Summary

Fields
Modifier and Type	Field and Description
`protected double[]`	`max` maximum of each dimension.
`protected double[]`	`min` minimum of each dimension.
`protected int`	`n` the number of dimensions.
`protected KDTreeNode<T>`	`root`
`protected long`	`size` the number of nodes in the tree.

Constructor Summary

Constructors
Constructor and Description
`KDTree(IterableRealInterval<T> interval)` Construct a KDTree from the elements of the given `IterableRealInterval`.
`KDTree(List<T> values, List<L> positions)` Construct a KDTree from the elements in the given list.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`KDTree.KDTreeCursor`	`cursor()` Returns a `RealCursor` that iterates with optimal speed without calculating the location at each iteration step.
`T`	`firstElement()` Get the first element of this `IterableRealInterval`.
`KDTreeNode<T>`	`getRoot()` Get the root node.
`Object`	`iterationOrder()` Returns the iteration order of this `IterableRealInterval`.
`KDTree.KDTreeCursor`	`iterator()`
`KDTree.KDTreeCursor`	`localizingCursor()` Returns a `RealLocalizable` `Iterator` that calculates its location at each iteration step.
`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[])`.
`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.
`protected <L extends RealLocalizable> KDTree.ValueNode<T>`	`makeNode(ListIterator<L> first, ListIterator<L> last, int d)` See `makeNode(ListIterator, ListIterator, int, List, int[])`.
`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.
`protected KDTree.SamplerNode<T>`	`makeSamplerNode(List<RealCursor<T>> elements, int i, int j, int d)` Construct the tree by recursively adding nodes.
`int`	`numDimensions()` Gets the space's number of dimensions.
`void`	`realMax(double[] m)` Write the maximum of each dimension into double[].
`double`	`realMax(int d)` Get the maximum in dimension d.
`void`	`realMax(RealPositionable m)` Sets a `RealPositionable` to the maximum of this `Interval`
`void`	`realMin(double[] m)` Write the minimum of each dimension into double[].
`double`	`realMin(int d)` Get the minimum in dimension d.
`void`	`realMin(RealPositionable m)` Sets a `RealPositionable` to the minimum of this `Interval`
`long`	`size()` Returns the number of elements in this `Function`.
`String`	`toString()`
`String`	`toString(KDTreeNode<T> left, String indent)`
`protected static <L extends RealLocalizable> boolean`	`verifyDimensions(List<L> positions, int n)` Check whether all positions in the positions list have dimension n.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface net.imglib2.RealInterval
maxAsDoubleArray, maxAsRealPoint, minAsDoubleArray, minAsRealPoint

Methods inherited from interface java.lang.Iterable
forEach, spliterator

- Field Detail
  - 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 Detail
  - 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 Detail
  - 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
  - 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
  - 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
  - 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
  - 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:
    
    FlatIterationOrder
  - iterator
```
public KDTree.KDTreeCursor iterator()
```
    Specified by:
    
    iterator in interface Iterable<T>
  - cursor
```
public KDTree.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.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.

Class KDTree<T>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface net.imglib2.RealInterval

Methods inherited from interface java.lang.Iterable

Field Detail

n

root

size

min

max

Constructor Detail

KDTree

KDTree

Method Detail

verifyDimensions

makeNode

makeNode

makeNode

makeNode

makeSamplerNode

getRoot

numDimensions

toString

toString

realMin

realMin

realMin

realMax

realMax

realMax

size

iterationOrder

iterator

cursor

localizingCursor

firstElement