Class KDTreeUtils

java.lang.Object

net.imglib2.kdtree.KDTreeUtils

final class KDTreeUtils
extends Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static final class	KDTreeUtils.MakeTree

Field Summary

Fields

Modifier and Type	Field	Description
(package private) static final int	MAX_ARRAY_SIZE

Constructor Summary

Constructors

Modifier	Constructor	Description
private	KDTreeUtils()

Method Summary

Modifier and Type	Method	Description
(package private) static void	computeMinMax(double[][] positions, double[] min, double[] max)	Compute bounding box of positions in nested layout
(package private) static void	computeMinMax(double[] flatPositions, double[] min, double[] max)	Compute bounding box of positions in flat layout
(package private) static double[]	flatten(double[][] positions)	Flatten the nested positions array.
(package private) static int	getNumDimensions(Iterable<? extends RealLocalizable> positions)	Returns the number of dimensions of the first element of positions.
(package private) static <T> T	getType(Iterable<T> values)	Returns the first element of values.
(package private) static double[][]	initPositions(int numDimensions, int numPoints, Iterable<? extends RealLocalizable> points)	Copy the coordinates of the given points to a new double[][] positions array.
(package private) static int[]	invert(int[] tree)	Invert the given permutation tree.
(package private) static int	leftChildIndex(int i)	If the tree is flattened into an array the left child of node at index i has index 2 * i + 1.
(package private) static int[]	makeTree(double[][] positions)	Sort the given points into a k-d tree.
(package private) static <T extends NativeType<T>> Img<T>	orderValuesImg(int[] invtree, Iterable<T> values)	Re-order the node values to form a tree corresponding to the index array tree'={0,1,2,...}.
(package private) static <T> List<T>	orderValuesList(int[] invtree, Iterable<T> values)	Re-order the node values to form a tree corresponding to the index array tree'={0,1,2,...}.
(package private) static int	parentIndex(int i)	If the tree is flattened into an array the parent of node at index i has index (i - 1) / 2 (except for the root node i==0).
(package private) static int	partition(int i, int j, double[] values, int[] order)	Partition a sublist.
(package private) static void	quicksort(int i, int j, double[] values, int[] order)	Sort a sublist.
(package private) static double[][]	reorder(double[][] positions, int[] tree)	Re-order the node positions to form a tree corresponding to the index array tree'={0,1,2,...}.
(package private) static double[]	reorder(double[] values, int[] order)	Create a new double[] array that contains the elements of values, ordered such that values[order[i]] is at index i.
(package private) static int[]	reorder(int[] values, int[] order)	Create a new int[] array that contains the elements of values, ordered such that values[order[i]] is at index i.
(package private) static double[]	reorderToFlatLayout(double[][] positions, int[] tree)	Re-order the node positions to form a tree corresponding to the index array tree={0,1,2,...}.
(package private) static int	rightChildIndex(int i)	If the tree is flattened into an array the right child of node at index i has index 2 * i + 2.
private static void	swap(int i, int j, int[] order)	Swap order[i] and order[j].
(package private) static double[][]	unflatten(double[] positions, int n)	Transform flat positions array into a nested double[numDimensions][numPoints] array.

Methods inherited from class Object

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

Field Details

MAX_ARRAY_SIZE

static final int MAX_ARRAY_SIZE

See Also:

• Constant Field Values

Constructor Details

KDTreeUtils

private KDTreeUtils()

Method Details

leftChildIndex

static int leftChildIndex(int i)

If the tree is flattened into an array the left child of node at index i has index 2 * i + 1.

rightChildIndex

static int rightChildIndex(int i)

If the tree is flattened into an array the right child of node at index i has index 2 * i + 2.

parentIndex

static int parentIndex(int i)

If the tree is flattened into an array the parent of node at index i has index (i - 1) / 2 (except for the root node i==0).

initPositions

static double[][] initPositions(int numDimensions,
 int numPoints,
 Iterable<? extends RealLocalizable> points)

Copy the coordinates of the given points to a new double[][] positions array. The coordinate in dimension d of the ith point is stored at positions[d][i]. That is, positions[0] has all X coordinates, positions[0] has all Y coordinates, and so on.

makeTree

static int[] makeTree(double[][] positions)

Sort the given points into a k-d tree.

The tree is given as a flat (heap-like) array of point indices, int[] tree. The index of the point chosen as the root node is tree[0]. The coordinates of the root node are at positions[d][tree[0]].

The indices of the children (less-or-equal and greater-or-equal, respectively) of root are at tree[1] and tree[2], and so on.

Parameters:

positions - The coordinates for the ith point are stored at positions[d][i] where d is the dimension. See initPositions(int, int, Iterable).

Returns:

flattened tree of point indices

reorder

static double[][] reorder(double[][] positions,
 int[] tree)

Re-order the node positions to form a tree corresponding to the index array tree'={0,1,2,...}.

Parameters:

positions -

tree -

Returns:

reorder

static double[] reorder(double[] values,
 int[] order)

Create a new double[] array that contains the elements of values, ordered such that values[order[i]] is at index i.

reorder

static int[] reorder(int[] values,
 int[] order)

Create a new int[] array that contains the elements of values, ordered such that values[order[i]] is at index i.

reorderToFlatLayout

static double[] reorderToFlatLayout(double[][] positions,
 int[] tree)

Re-order the node positions to form a tree corresponding to the index array tree={0,1,2,...}. Then flatten the result into a 1-D array, interleaving coordinates in all dimensions.

Parameters:

positions -

tree -

Returns:

flatten

static double[] flatten(double[][] positions)

Flatten the nested positions array.

Parameters:

positions - positions in nested layout

Returns:

positions in flattened layout

unflatten

static double[][] unflatten(double[] positions,
 int n)

Transform flat positions array into a nested double[numDimensions][numPoints] array.

With flat layout, positions are stored as a flat double[] array, where positions[d + i*n] is dimension d of the i-th point, with n the number of dimensions.

With nested layout, positions are stored as a nested double[][] array where positions[d][i] is dimension d of the i-th point.

Parameters:

positions - positions in flattened layout

n - number of dimensions

Returns:

positions in nested layout

computeMinMax

static void computeMinMax(double[][] positions,
 double[] min,
 double[] max)

Compute bounding box of positions in nested layout

computeMinMax

static void computeMinMax(double[] flatPositions,
 double[] min,
 double[] max)

Compute bounding box of positions in flat layout

invert

static int[] invert(int[] tree)

Invert the given permutation tree.

For example, tree = {3, 4, 1, 0, 5, 2} indicates that coordinates and value for the node at heap index i can be found at index tree[i] in the respective input list.

The inverse, inv = {3, 4, 1, 0, 5, 2} indicates that coordinates and value at index i in the respective input list belong to the node at heap index inv[i].

Parameters:

tree - a permutation

Returns:

the inverse permutation

orderValuesList

static <T> List<T> orderValuesList(int[] invtree,
 Iterable<T> values)

Re-order the node values to form a tree corresponding to the index array tree'={0,1,2,...}. The tree is given as an inverted permutation, so that we can iterate through the values in order, putting each at the right index in the returned List.

Type Parameters:

T -

Parameters:

invtree -

values -

Returns:

orderValuesImg

static <T extends NativeType<T>> Img<T> orderValuesImg(int[] invtree,
 Iterable<T> values)

Re-order the node values to form a tree corresponding to the index array tree'={0,1,2,...}. The tree is given as an inverted permutation, so that we can iterate through the values in order, putting each at the right index in the returned 1D Img.

Type Parameters:

T -

Parameters:

invtree -

values -

Returns:

getType

static <T> T getType(Iterable<T> values)

Returns the first element of values.

Throws:

IllegalArgumentException - if values has no elements.

getNumDimensions

static int getNumDimensions(Iterable<? extends RealLocalizable> positions)

Returns the number of dimensions of the first element of positions. If positions has no elements, returns 0.

Parameters:

positions - list of points

Returns:

number of dimensions of the first point

swap

private static void swap(int i,
 int j,
 int[] order)

Swap order[i] and order[j].

partition

static int partition(int i,
 int j,
 double[] values,
 int[] order)

Partition a sublist. The list is given by an immutable array of values, and an index array that represents the order of values in the list. This method only rearranges the order array.

A pivot element is chosen by median-of-three method. Then [i,j] is reordered, such that all elements before the pivot are smaller-equal and all elements after the pivot are larger-equal the pivot. The index of the pivot element is returned.

Parameters:

i - index of first element of the sublist

j - index of last element of the sublist

values - the array of values of list elements.

order - order of list elements. E.g., order[0]=3 means that values[3] is the first element of the list.

Returns:

index of pivot element

quicksort

static void quicksort(int i,
 int j,
 double[] values,
 int[] order)

Sort a sublist. The list is given by an immutable array of values, and an index array that represents the order of values in the list. This method only rearranges the order array.

Parameters:

i - index of first element of the sublist

j - index of last element of the sublist

values - the array of values of list elements.

order - order of list elements. E.g., order[0]=3 means that values[3] is the first element of the list.