org.ddogleg.nn.alg

Class KdTree

java.lang.Object

org.ddogleg.nn.alg.KdTree

public class KdTree
extends java.lang.Object

K-D Tree is short for k-dimensional tree and is a binary tree data structure used for quickly finding the nearest-neighbor of a k-dimensional point in a set. Each point can optionally have data associated with it. The tree is structured such that at each node has a point and two children. All points in the set with values <= to the node's point in the specified dimension/axis are on the the left and >= to the right. A leaf will have no children.

NOTE: If multiple points have identical values then there will be a node for each point.

NOTE: If there is more than one point with an identical value to the node's point, then the identical points can go in either the left or right branches.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KdTree.Node Data type for each node in the binary tree.

Constructor Summary

Constructors

Constructor and Description
KdTree()
KdTree(int N) Specifies the type of points it can process.

Method Summary

Modifier and Type	Method and Description
static double	distanceSq(KdTree.Node a, double[] point, int N) Euclidean distance squared between the node's point and a point.

Methods inherited from class java.lang.Object

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

Constructor Detail

KdTree

public KdTree(int N)

Specifies the type of points it can process.

Parameters:

N - Number of elements in a point

KdTree

public KdTree()

Method Detail

distanceSq

public static double distanceSq(KdTree.Node a,
                                double[] point,
                                int N)

Euclidean distance squared between the node's point and a point.

Parameters:

a - Node in the graph

point - A point

Returns:

Euclidean distance squared.