jigl.image.utils
Class KdTree

java.lang.Object
  |
  +--jigl.image.utils.KdTree

public class KdTree

extends Object

This class does kdTree operations. A KD Tree is a data structure that is used in computer science during orthogonal range searching. For instance, when you want to find the set of points that fall into a given rectangle in a plane, using KD Tree it is possible to find the resulting points in O(sqrt(n)+k) time where n is the number of points and k is the number of points in the result.

Field Summary

private int	determine
private int	dimension The number of dimensions
private KdTree	left left branch of the tree
private KdTree	right Right branch of the tree
KdTree	root the root node of the tree
private float[]	value value at the node
Vector	values store the value of nearest neighbors

Constructor Summary

KdTree(int dimensions)
Construct a KdTree object with dimensions dimensions.

Method Summary

void	addNode(float[] node, KdTree tree) Adds a node to the correct place in the KdTree
void	buildTreePalette(RealColorImage image) Builds a KdTree from the colors in the image
void	findNearest(float[] node, KdTree tree, int threshold) Finds the nearest neighbor of node.
KdTree	getLeft() Returns the left child.
KdTree	getRight() Returns the right child.
float[]	getValue() Returns the value of the kdtree.

Methods inherited from class java.lang.Object

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

Field Detail

determine

private int determine

left

private KdTree left

left branch of the tree

right

private KdTree right

Right branch of the tree

value

private float[] value

value at the node

dimension

private int dimension

The number of dimensions

root

public KdTree root

the root node of the tree

values

public Vector values

store the value of nearest neighbors

Constructor Detail

KdTree

public KdTree(int dimensions)

Construct a KdTree object with dimensions dimensions.

Method Detail

getLeft

public KdTree getLeft()

Returns the left child.

getRight

public KdTree getRight()

Returns the right child.

getValue

public float[] getValue()

Returns the value of the kdtree.

findNearest

public void findNearest(float[] node,
                        KdTree tree,
                        int threshold)

Finds the nearest neighbor of node. Threshold is nessasary because if the threshold is too low, a value is not always returned. If threshold is too high, then too many values are returned.

buildTreePalette

public void buildTreePalette(RealColorImage image)

Builds a KdTree from the colors in the image

addNode

public void addNode(float[] node,
                    KdTree tree)

Adds a node to the correct place in the KdTree