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:

java.lang.Iterable<T>, EuclideanSpace, IterableRealInterval<T>, RealInterval

public class KDTree<T>
extends java.lang.Object
implements EuclideanSpace, IterableRealInterval<T>

KDTree to access values at RealLocalizable positions.

Nested Class Summary

Nested Classes

Modifier and Type	Class	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 its value as a Sampler.
protected static class	KDTree.ValueNode<T>	A KDTreeNode that stores its value as a reference.

Field Summary

Fields

Modifier and Type	Field	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	Description
KDTree(java.util.List<T> values, java.util.List<L> positions)	Construct a KDTree from the elements in the given list.
KDTree(IterableRealInterval<T> interval)	Construct a KDTree from the elements of the given IterableRealInterval.

Method Summary

Modifier and Type	Method	Description
KDTree.KDTreeCursor	cursor()	Returns a RealCursor that iterates with optimal speed without calculating the location at each iteration step.
KDTreeNode<T>	getRoot()	Get the root node.
java.lang.Object	iterationOrder()	Returns the iteration order of this IterableRealInterval.
KDTree.KDTreeCursor	localizingCursor()	Returns a RealLocalizable Iterator that calculates its location at each iteration step.
protected <L extends RealLocalizable> KDTree.ValueNode<T>	makeNode(java.util.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(java.util.List<L> positions, int i, int j, int d, java.util.List<T> values, int[] permutation)	Construct the tree by recursively adding nodes.
protected <L extends RealLocalizable> KDTree.ValueNode<T>	makeNode(java.util.ListIterator<L> first, java.util.ListIterator<L> last, int d)	See makeNode(ListIterator, ListIterator, int, List, int[]).
protected <L extends RealLocalizable> KDTree.ValueNode<T>	makeNode(java.util.ListIterator<L> first, java.util.ListIterator<L> last, int d, java.util.List<T> values, int[] permutation)	Construct the tree by recursively adding nodes.
protected KDTree.SamplerNode<T>	makeSamplerNode(java.util.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.
java.lang.String	toString()
java.lang.String	toString(KDTreeNode<T> left, java.lang.String indent)
protected static <L extends RealLocalizable> boolean	verifyDimensions(java.util.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 java.lang.Iterable

forEach, spliterator

Methods inherited from interface net.imglib2.IterableRealInterval

firstElement, iterator

Methods inherited from interface net.imglib2.RealInterval

maxAsDoubleArray, maxAsRealPoint, minAsDoubleArray, minAsRealPoint

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(java.util.List<T> values,
              java.util.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(java.util.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(java.util.List<L> positions,
                                                                   int i,
                                                                   int j,
                                                                   int d,
                                                                   java.util.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(java.util.ListIterator<L> first,
                                                                   java.util.ListIterator<L> last,
                                                                   int d,
                                                                   java.util.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(java.util.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(java.util.ListIterator<L> first,
                                                                   java.util.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(java.util.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 java.lang.String toString(KDTreeNode<T> left,
                                 java.lang.String indent)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.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 java.lang.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

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