KDTreeT Class 
Namespace: Accord.Collections
The KDTreeT type exposes the following members.
Name  Description  

KDTreeT(Int32) 
Creates a new KDTreeT.
 
KDTreeT(Int32, KDTreeNodeT) 
Creates a new KDTreeT.
 
KDTreeT(Int32, KDTreeNodeT, Int32, Int32) 
Creates a new KDTreeT.

Name  Description  

Count 
Gets the number of elements contained in this
tree. This is also the number of tree nodes.
(Inherited from KDTreeBaseTNode.)  
Dimensions 
Gets the number of dimensions expected
by the input points of this tree.
(Inherited from KDTreeBaseTNode.)  
Distance 
Gets or set the distance function used to
measure distances amongst points on this tree
(Inherited from KDTreeBaseTNode.)  
Leaves 
Gets the number of leaves contained in this
tree. This can be used to calibrate approximate
nearest searchers.
(Inherited from KDTreeBaseTNode.)  
Root 
Gets the root node of this tree.
(Inherited from BinaryTreeTNode.) 
Name  Description  

Add 
Inserts a value in the tree at the desired position.
 
AddNode 
Inserts a value into the tree at the desired position.
(Inherited from KDTreeBaseTNode.)  
ApproximateNearest(Double, Double) 
Retrieves a percentage of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)  
ApproximateNearest(Double, Int32) 
Retrieves a fixed number of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)  
ApproximateNearest(Double, Double, Double) 
Retrieves a percentage of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)  
ApproximateNearest(Double, Int32, Double) 
Retrieves a fixed percentage of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)  
ApproximateNearest(Double, Int32, Int32) 
Retrieves a fixed number of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)  
Clear 
Removes all nodes from this tree.
(Inherited from KDTreeBaseTNode.)  
CopyTo 
Copies the entire tree to a compatible onedimensional Array, starting
at the specified arrayIndex of the array.
(Inherited from KDTreeBaseTNode.)  
Equals  Determines whether the specified object is equal to the current object. (Inherited from Object.)  
Finalize  Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection. (Inherited from Object.)  
GetEnumerator 
Returns an enumerator that iterates through the tree.
(Inherited from BinaryTreeTNode.)  
GetHashCode  Serves as the default hash function. (Inherited from Object.)  
GetNodesInsideRegion 
Retrieves a list of all points inside a given region.
(Inherited from KDTreeBaseTNode.)  
GetType  Gets the Type of the current instance. (Inherited from Object.)  
MemberwiseClone  Creates a shallow copy of the current Object. (Inherited from Object.)  
Nearest(Double) 
Retrieves the nearest point to a given point.
(Inherited from KDTreeBaseTNode.)  
Nearest(Double, Double) 
Retrieves the nearest points to a given point within a given radius.
(Inherited from KDTreeBaseTNode.)  
Nearest(Double, Double) 
Retrieves the nearest point to a given point.
(Inherited from KDTreeBaseTNode.)  
Nearest(Double, Int32) 
Retrieves a fixed number of nearest points to a given point.
(Inherited from KDTreeBaseTNode.)  
Nearest(Double, Double, Int32) 
Retrieves the nearest points to a given point within a given radius.
(Inherited from KDTreeBaseTNode.)  
ToString  Returns a string that represents the current object. (Inherited from Object.)  
Traverse 
Traverse the tree using a tree traversal
method. Can be iterated with a foreach loop.
(Inherited from BinaryTreeTNode.) 
Name  Description  

HasMethod 
Checks whether an object implements a method with the given name.
(Defined by ExtensionMethods.)  
IsEqual  Compares two objects for equality, performing an elementwise comparison if the elements are vectors or matrices. (Defined by Matrix.)  
ToT 
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.) 
A kd tree (short for kdimensional tree) is a spacepartitioning data structure for organizing points in a kdimensional space. kd 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). kd trees are a special case of binary space partitioning trees.
The kd tree is a binary tree in which every node is a kdimensional point. Every non leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as halfspaces. 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 kdimensions, 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 xvalue of the point, and its normal would be the unit xaxis.
References:
// This is the same example found in Wikipedia page on // kd trees: http://en.wikipedia.org/wiki/Kd_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);