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
KDTree to access values at RealLocalizable positions.
- Author:
- Tobias Pietzsch
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic final class
KDTree.DimComparator<L extends RealLocalizable>
Compare RealLocalizables by comparing their coordinates in dimension d.final class
protected static final class
A KDTreeNode that stores it's value as a Sampler.protected static final class
A KDTreeNode that stores it's value as a reference. -
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionConstruct a KDTree from the elements in the given list.KDTree
(IterableRealInterval<T> interval) Construct a KDTree from the elements of the givenIterableRealInterval
. -
Method Summary
Modifier and TypeMethodDescriptioncursor()
Returns aRealCursor
that iterates with optimal speed without calculating the location at each iteration step.Get the first element of thisIterableRealInterval
.getRoot()
Get the root node.Returns the iteration order of thisIterableRealInterval
.iterator()
Returns aRealLocalizable
Iterator
that calculates its location at each iteration step.protected <L extends RealLocalizable>
KDTree.ValueNode<T> protected <L extends RealLocalizable>
KDTree.ValueNode<T> Construct the tree by recursively adding nodes.protected <L extends RealLocalizable>
KDTree.ValueNode<T> makeNode
(ListIterator<L> first, ListIterator<L> last, int d) 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
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
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
Sets aRealPositionable
to the minimum of thisInterval
long
size()
Returns the number of elements in thisFunction
.toString()
toString
(KDTreeNode<T> left, String indent) protected static <L extends RealLocalizable>
booleanverifyDimensions
(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
-
Field Details
-
n
protected final int nthe number of dimensions. -
root
-
size
protected final long sizethe number of nodes in the tree. -
min
protected final double[] minminimum of each dimension. -
max
protected final double[] maxmaximum of each dimension.
-
-
Constructor Details
-
KDTree
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
Construct a KDTree from the elements of the givenIterableRealInterval
.- Parameters:
interval
- elements in the tree are obtained by iterating this
-
-
Method Details
-
verifyDimensions
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 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(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 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(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(ListIterator<L> first, 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
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
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
-
toString
-
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
- Parameters:
m
-
-
realMin
Description copied from interface:RealInterval
Sets aRealPositionable
to the minimum of thisInterval
- Specified by:
realMin
in interfaceRealInterval
- Parameters:
m
-
-
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
- Parameters:
m
-
-
realMax
Description copied from interface:RealInterval
Sets aRealPositionable
to the maximum of thisInterval
- Specified by:
realMax
in interfaceRealInterval
- Parameters:
m
-
-
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
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:
-
iterator
-
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
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
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.
-