Click or drag to resize
Accord.NET (logo)

KDTreeT Class

K-dimensional tree.
Inheritance Hierarchy
SystemObject
  Accord.CollectionsBinaryTreeKDTreeNodeT
    Accord.CollectionsKDTreeBaseKDTreeNodeT
      Accord.CollectionsKDTreeT

Namespace:  Accord.Collections
Assembly:  Accord.MachineLearning (in Accord.MachineLearning.dll) Version: 3.7.0
Syntax
[SerializableAttribute]
public class KDTree<T> : KDTreeBase<KDTreeNode<T>>
Request Example View Source

Type Parameters

T
The type of the value being stored.

The KDTreeT type exposes the following members.

Constructors
Properties
Methods
  NameDescription
Public methodAdd
Inserts a value in the tree at the desired position.
Protected methodAddNode
Inserts a value into the tree at the desired position.
(Inherited from KDTreeBaseTNode.)
Public methodApproximateNearest(Double, Double)
Retrieves a percentage of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)
Public methodApproximateNearest(Double, Int32)
Retrieves a fixed number of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)
Public methodApproximateNearest(Double, Double, Double)
Retrieves a percentage of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)
Public methodApproximateNearest(Double, Int32, Double)
Retrieves a fixed percentage of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)
Public methodApproximateNearest(Double, Int32, Int32)
Retrieves a fixed number of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)
Public methodClear
Removes all nodes from this tree.
(Inherited from KDTreeBaseTNode.)
Public methodCopyTo
Copies the entire tree to a compatible one-dimensional Array, starting at the specified arrayIndex of the array.
(Inherited from KDTreeBaseTNode.)
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetEnumerator
Returns an enumerator that iterates through the tree.
(Inherited from BinaryTreeTNode.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetNodesInsideRegion
Retrieves a list of all points inside a given region.
(Inherited from KDTreeBaseTNode.)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodNearest(Double)
Retrieves the nearest point to a given point.
(Inherited from KDTreeBaseTNode.)
Public methodNearest(Double, Double)
Retrieves the nearest points to a given point within a given radius.
(Inherited from KDTreeBaseTNode.)
Public methodNearest(Double, Double)
Retrieves the nearest point to a given point.
(Inherited from KDTreeBaseTNode.)
Public methodNearest(Double, Int32)
Retrieves a fixed number of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)
Public methodNearest(Double, Double, Int32)
Retrieves the nearest points to a given point within a given radius.
(Inherited from KDTreeBaseTNode.)
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Public methodTraverse
Traverse the tree using a tree traversal method. Can be iterated with a foreach loop.
(Inherited from BinaryTreeTNode.)
Top
Extension Methods
  NameDescription
Public Extension MethodHasMethod
Checks whether an object implements a method with the given name.
(Defined by ExtensionMethods.)
Public Extension MethodIsEqual
Compares two objects for equality, performing an elementwise comparison if the elements are vectors or matrices.
(Defined by Matrix.)
Public Extension MethodToT
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by ExtensionMethods.)
Top
Remarks

A k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

The k-d tree is a binary tree in which every node is a k-dimensional point. Every non- leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as half-spaces. Points to the left of this hyperplane represent the left subtree of that node and points right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the x-value of the point, and its normal would be the unit x-axis.

References:

  • Wikipedia, The Free Encyclopedia. K-d tree. Available on: http://en.wikipedia.org/wiki/K-d_tree
  • Moore, Andrew W. "An intoductory tutorial on kd-trees." (1991). Available at: http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf

Examples
// This is the same example found in Wikipedia page on
// k-d trees: http://en.wikipedia.org/wiki/K-d_tree

// Suppose we have the following set of points:

double[][] points =
{
    new double[] { 2, 3 },
    new double[] { 5, 4 },
    new double[] { 9, 6 },
    new double[] { 4, 7 },
    new double[] { 8, 1 },
    new double[] { 7, 2 },
};


// To create a tree from a set of points, we use
KDTree<int> tree = KDTree.FromData<int>(points);

// Now we can manually navigate the tree
KDTreeNode<int> node = tree.Root.Left.Right;

// Or traverse it automatically
foreach (KDTreeNode<int> n in tree)
{
    double[] location = n.Position;
    Assert.AreEqual(2, location.Length);
}

// Given a query point, we can also query for other
// points which are near this point within a radius

double[] query = new double[] { 5, 3 };

// Locate all nearby points within an euclidean distance of 1.5
// (answer should be be a single point located at position (5,4))
KDTreeNodeCollection<int> result = tree.Nearest(query, radius: 1.5); 

// We can also use alternate distance functions
tree.Distance = Accord.Math.Distance.Manhattan;

// And also query for a fixed number of neighbor points
// (answer should be the points at (5,4), (7,2), (2,3))
KDTreeNodeCollection<int> neighbors = tree.Nearest(query, neighbors: 3);
See Also