net.imglib2.kdtree

Class KDTreeImpl

java.lang.Object

net.imglib2.kdtree.KDTreeImpl

public class KDTreeImpl
extends Object

Represents the tree structure, and provides access to node coordinates (but not values).

The nodes in the tree are arranged in Eytzinger layout (children of i are at 2i and 2i+1). Additionally, pivot indices are chosen such 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.

Constructor Summary

Constructors

Constructor and Description
KDTreeImpl(KDTreePositions positions)

Method Summary

Modifier and Type	Method and Description
int	depth()
double	getDoublePosition(int i, int d)
int	left(int i) Get the left child of node i.
int	numDimensions()
int	parent(int i) Get the parent of node i.
int	right(int i) Get the right child of node i.
int	root() Get the root node of the tree.
int	size()
int	splitDimension(int i) Get the dimension along which node i divides the space.
double	squDistance(int i, double[] pos) Compute the squared distance from node i to pos.
float	squDistance(int i, float[] pos) Compute the squared distance from node i to pos.
double	squDistance(int i, RealLocalizable pos) Compute the squared distance from node i to pos.

Methods inherited from class java.lang.Object

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

Constructor Detail

KDTreeImpl

public KDTreeImpl(KDTreePositions positions)

Method Detail

root

public int root()

Get the root node of the tree.

Returns:

index of the root node

left

public int left(int i)

Get the left child of node i.

Parameters:

i - node index

Returns:

index of left child or -1 if no left child exists

right

public int right(int i)

Get the right child of node i.

Parameters:

i - node index

Returns:

index of right child or -1 if no right child exists

parent

public int parent(int i)

Get the parent of node i.

Parameters:

i - node index

Returns:

index of parent

splitDimension

public int splitDimension(int i)

Get the dimension along which node i divides the space.

Parameters:

i - node index

Returns:

splitting dimension.

getDoublePosition

public double getDoublePosition(int i,
                                int d)

squDistance

public float squDistance(int i,
                         float[] pos)

Compute the squared distance from node i to pos.

squDistance

public double squDistance(int i,
                          double[] pos)

Compute the squared distance from node i to pos.

squDistance

public double squDistance(int i,
                          RealLocalizable pos)

Compute the squared distance from node i to pos.

numDimensions

public int numDimensions()

size

public int size()

depth

public int depth()