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.- Author:
- Tobias Pietzsch
-
-
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 it's value as a Sampler.protected static class
KDTree.ValueNode<T>
A KDTreeNode that stores it's value as a reference.
-
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 givenIterableRealInterval
.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description KDTree.KDTreeCursor
cursor()
Returns aRealCursor
that iterates with optimal speed without calculating the location at each iteration step.T
firstElement()
Get the first element of thisIterableRealInterval
.KDTreeNode<T>
getRoot()
Get the root node.java.lang.Object
iterationOrder()
Returns the iteration order of thisIterableRealInterval
.KDTree.KDTreeCursor
iterator()
KDTree.KDTreeCursor
localizingCursor()
Returns aRealLocalizable
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)
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)
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 aRealPositionable
to the maximum of thisInterval
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 aRealPositionable
to the minimum of thisInterval
long
size()
Returns the number of elements in thisFunction
.java.lang.String
toString()
java.lang.String
toString(KDTreeNode<T> left, java.lang.String indent)
protected static <L extends RealLocalizable>
booleanverifyDimensions(java.util.List<L> positions, int n)
Check whether all positions in the positions list have dimension n.
-
-
-
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
ifT extends RealLocalizable
.- Parameters:
values
- a list of valuespositions
- a list of positions corresponding to the values
-
KDTree
public KDTree(IterableRealInterval<T> interval)
Construct a KDTree from the elements of the givenIterableRealInterval
.- 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 positionsi
- start index of sublist to processj
- end index of sublist to processd
- dimension along which to split the sublistvalues
- list of values corresponding to permuted positionspermutation
- 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 positionslast
- last element of the sublist of positionsd
- dimension along which to split the sublistvalues
- list of values corresponding to permuted positionspermutation
- 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)
SeemakeNode(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 processj
- end index of sublist to processd
- 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)
SeemakeNode(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 processlast
- last element of the sublist to processd
- 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 processj
- end index of sublist to processd
- 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 interfaceEuclideanSpace
-
toString
public java.lang.String toString(KDTreeNode<T> left, java.lang.String indent)
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
realMin
public double realMin(int d)
Description copied from interface:RealInterval
Get the minimum in dimension d.- Specified by:
realMin
in interfaceRealInterval
- 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 interfaceRealInterval
-
realMin
public void realMin(RealPositionable m)
Description copied from interface:RealInterval
Sets aRealPositionable
to the minimum of thisInterval
- Specified by:
realMin
in interfaceRealInterval
-
realMax
public double realMax(int d)
Description copied from interface:RealInterval
Get the maximum in dimension d.- Specified by:
realMax
in interfaceRealInterval
- 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 interfaceRealInterval
-
realMax
public void realMax(RealPositionable m)
Description copied from interface:RealInterval
Sets aRealPositionable
to the maximum of thisInterval
- Specified by:
realMax
in interfaceRealInterval
-
size
public long size()
Description copied from interface:IterableRealInterval
Returns the number of elements in this
Function
.- Specified by:
size
in interfaceIterableRealInterval<T>
- Returns:
- number of elements
-
iterationOrder
public java.lang.Object iterationOrder()
Description copied from interface:IterableRealInterval
Returns the iteration order of thisIterableRealInterval
. If the returned object equals (Object.equals(Object)
) the iteration order of anotherIterableRealInterval
f then they can be copied by synchronous iteration. That is, having anIterator
on this and anotherIterator
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 interfaceIterableRealInterval<T>
- Returns:
- the iteration order of this
IterableRealInterval
. - See Also:
FlatIterationOrder
-
iterator
public KDTree.KDTreeCursor iterator()
- Specified by:
iterator
in interfacejava.lang.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 interfaceIterableRealInterval<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 interfaceIterableRealInterval<T>
- Returns:
- fast localizing iterator
-
firstElement
public T firstElement()
Description copied from interface:IterableRealInterval
Get the first element of thisIterableRealInterval
. This is a shortcut forcursor().next()
. This can be used to create a new variable of type T usingfirstElement().createVariable()
, which is useful in generic methods to store temporary results, e.g., a running sum over pixels in theIterableRealInterval
.- Specified by:
firstElement
in interfaceIterableRealInterval<T>
- Returns:
- the first element in iteration order.
-
-