Class KDTreeUtils.MakeTree

java.lang.Object

net.imglib2.kdtree.KDTreeUtils.MakeTree

Enclosing class:

KDTreeUtils

private static final class KDTreeUtils.MakeTree
extends Object

Field Summary

Fields

Modifier and Type	Field	Description
private final int[]	indices	Temporary array to keep track of elements.
private final int	numDimensions
private final int	numPoints
private final double[][]	positions	The coordinates for the ith point are stored at positions[d][k] where d is the dimension.
private final int[]	tree	Node indices in a flattened (heap-like) array.

Constructor Summary

Constructors

Modifier	Constructor	Description
private	MakeTree(double[][] positions)

Method Summary

Modifier and Type	Method	Description
private void	kthElement(int i, int j, int k, int compare_d)	Partition a sublist of Nodes by their coordinate in the specified dimension, such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
private void	makeNode(int i, int j, int d, int nodeIndex)
private static int	pivot(int len)	Calculate pivot index such that the tree will be arranged in a way that "leaf layers" are filled from the left.

Methods inherited from class Object

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

Field Details

numDimensions

private final int numDimensions

numPoints

private final int numPoints

positions

private final double[][] positions

The coordinates for the ith point are stored at positions[d][k] where d is the dimension.

indices

private final int[] indices

Temporary array to keep track of elements. Initialized to 0, 1, ... and then permuted when sorting the elements into a tree.

tree

private final int[] tree

Node indices in a flattened (heap-like) array. For example: the index of the root node is tree[0]. The coordinates of the root node are at positions[d][tree[0]] where d is the dimension. The children of the root node are at tree[1] and tree[2], and so on.

Constructor Details

MakeTree

private MakeTree(double[][] positions)

Method Details

pivot

private static int pivot(int len)

Calculate pivot index such that the tree will be arranged in a way that "leaf layers" are filled from the left. For example 10 nodes will always be arranged like this:

           0
        /     \
      1         2
    /   \     /   \
   3     4   5     6
  / \   /
 7   8 9

never like this:

           0
        /     \
      1         2
    /   \     /   \
   3     4   5     6
  /         /     /
 7         8     9

By choosing pivots in this way, the tree structure is fully determined. For every node index, the child indices can be calculated without dependent reads. And iff the calculated child index is less than the number of nodes, the child exists.

makeNode

private void makeNode(int i,
 int j,
 int d,
 int nodeIndex)

kthElement

private void kthElement(int i,
 int j,
 int k,
 int compare_d)

Partition a sublist of Nodes by their coordinate in the specified dimension, such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.

Parameters:

i - index of first element of the sublist

j - index of last element of the sublist

k - index for k-th smallest value. i <= k <= j.

compare_d - dimension by which to order the sublist