Class KDTree<T>

java.lang.Object

net.imglib2.KDTree<T>

All Implemented Interfaces:

Iterable<T>, EuclideanSpace, IterableRealInterval<T>, RealInterval, Typed<T>

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
final class	KDTree.KDTreeCursor

Field Summary

Fields

Modifier and Type	Field	Description
(package private) final KDTreeImpl	impl
private static final int	MAX_ARRAY_SIZE
private final KDTreeData<T>	treeData

Constructor Summary

Constructors

Modifier	Constructor	Description
<L extends RealLocalizable>	KDTree(int numPoints, Iterable<T> values, Iterable<L> positions)
<L extends RealLocalizable>	KDTree(List<T> values, 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.
	KDTree(KDTreeData<T> data)

Method Summary

Modifier and Type	Method	Description
KDTreeNode<T>	createNode()	Create a re-usable KDTreeNode proxy linked to this tree.
KDTree<T>.KDTreeCursor	cursor()	Returns a RealCursor that iterates with optimal speed without calculating the location at each iteration step.
KDTreeNode<T>	getRoot()	Deprecated. KDTreeNode is now a re-usable proxy (like NativeType).
T	getType()	Get an instance of T.
KDTreeImpl	impl()	Access to pure coordinate kD Tree implementation.
Object	iterationOrder()	Returns the iteration order of this IterableRealInterval.
KDTree<T>.KDTreeCursor	iterator()
(package private) KDTreeNode<T>	left(KDTreeNode<T> parent)
KDTree<T>.KDTreeCursor	localizingCursor()	Returns a RealLocalizable Iterator that calculates its location at each iteration step.
int	numDimensions()	Gets the space's number of dimensions.
private static <A> Iterable<RealLocalizable>	positionsIterable(IterableRealInterval<A> sourceInterval)
double	realMax(int d)	Get the maximum in dimension d.
double	realMin(int d)	Get the minimum in dimension d.
(package private) KDTreeNode<T>	right(KDTreeNode<T> parent)
long	size()	Returns the number of elements in this Function.
String	toString()
private String	toString(int node, String indent, KDTreeNode<T> ref)
KDTreeData<T>	treeData()	Access to underlying data for serialization.
private static int	verifySize(List<?> values, List<?> positions)
private static int	verifySize(IterableRealInterval<?> interval)

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface Iterable

forEach

Methods inherited from interface IterableRealInterval

firstElement, localizingSpliterator, parallelStream, spliterator, stream

Methods inherited from interface RealInterval

maxAsDoubleArray, maxAsRealPoint, minAsDoubleArray, minAsRealPoint, realMax, realMax, realMin, realMin

Field Details

treeData

private final KDTreeData<T> treeData

impl

final KDTreeImpl impl

MAX_ARRAY_SIZE

private static final int MAX_ARRAY_SIZE

See Also:

• Constant Field Values

Constructor Details

KDTree

public <L extends RealLocalizable> 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

KDTree

public <L extends RealLocalizable> KDTree(int numPoints,
 Iterable<T> values,
 Iterable<L> positions)

KDTree

public KDTree(KDTreeData<T> data)

Method Details

treeData

public KDTreeData<T> treeData()

Access to underlying data for serialization.

impl

public KDTreeImpl impl()

Access to pure coordinate kD Tree implementation.

verifySize

private static int verifySize(List<?> values,
 List<?> positions)

verifySize

private static int verifySize(IterableRealInterval<?> interval)

positionsIterable

private static <A> Iterable<RealLocalizable> positionsIterable(IterableRealInterval<A> sourceInterval)

getRoot

@Deprecated
public KDTreeNode<T> getRoot()

Deprecated.

KDTreeNode is now a re-usable proxy (like NativeType). To work with existing code, KDTreeNode.left(), KDTreeNode.right(), getRoot() etc create new objects in each call, instead of re-using existing proxies. Code using that should be rewritten to reuse proxies, if possible.

Get the root node.

Returns:

the root node.

getType

public T getType()

Description copied from interface: IterableRealInterval

Get an instance of T.

It should not be assumed that the returned T instance is an independent copy. In particular, repeated calls to getType() may return the same instance.

The default implementation returns IterableRealInterval.firstElement(). Derived classes may choose different implementations for improved performance.

Specified by:

getType in interface IterableRealInterval<T>

Specified by:

getType in interface Typed<T>

Returns:

an instance of T

numDimensions

public int numDimensions()

Description copied from interface: EuclideanSpace

Gets the space's number of dimensions.

Specified by:

numDimensions in interface EuclideanSpace

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.

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.

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

iterator

public KDTree<T>.KDTreeCursor iterator()

Specified by:

iterator in interface Iterable<T>

Specified by:

iterator in interface IterableRealInterval<T>

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

toString

public String toString()

Overrides:

toString in class Object

toString

private String toString(int node,
 String indent,
 KDTreeNode<T> ref)

createNode

public KDTreeNode<T> createNode()

Create a re-usable KDTreeNode proxy linked to this tree. KDTreeNode.setNodeIndex(int) can be used to point the proxy to a particular node in the tree.

left

KDTreeNode<T> left(KDTreeNode<T> parent)

right

KDTreeNode<T> right(KDTreeNode<T> parent)