Class KdTree<T>
K-dimensional tree.
Inheritance
System.Object
Mars.Common.Core.Collections.SimpleTree.BinaryTree<
KdTreeNode<T>>
KdTree<T>
Implements
System.Collections.Generic.IEnumerable<
KdTreeNode<T>>
System.Collections.IEnumerable
Inherited Members
KdTreeBase<KdTreeNode<T>>.Nearest<T1, T2, T3>(Double[], Double, Int32, Func<KdTreeNode<T>, T1, T2, T3, Boolean>, T1, T2, T3)
Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.Root
Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.GetEnumerator()
Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.System.Collections.IEnumerable.GetEnumerator()
Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.SerializeJson()
Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.Deserialize(System.String)
Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.Traverse(Mars.Common.Core.Collections.SimpleTree.BinaryTraversalMethod<Mars.Common.Collections.KdTreeNode<T>>)
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Assembly: Mars.Common.dll
Syntax
[Serializable]
public class KdTree<T> : KdTreeBase<KdTreeNode<T>>, IEnumerable<KdTreeNode<T>>, IEnumerable
Type Parameters
Name |
Description |
T |
The type of the value being stored. |
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.Equal(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 = Mars.Numerics.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);
Constructors
KdTree(Int32)
Declaration
public KdTree(int dimensions)
Parameters
Type |
Name |
Description |
System.Int32 |
dimensions |
The number of dimensions in the tree. |
KdTree(Int32, KdTreeNode<T>)
Declaration
public KdTree(int dimension, KdTreeNode<T> root)
Parameters
Type |
Name |
Description |
System.Int32 |
dimension |
The number of dimensions in the tree. |
KdTreeNode<T> |
root |
The Root node, if already existent. |
KdTree(Int32, KdTreeNode<T>, Int32, Int32)
Declaration
public KdTree(int dimension, KdTreeNode<T> root, int count, int leaves)
Parameters
Type |
Name |
Description |
System.Int32 |
dimension |
The number of dimensions in the tree. |
KdTreeNode<T> |
root |
The Root node, if already existent. |
System.Int32 |
count |
The number of elements in the Root node. |
System.Int32 |
leaves |
The number of leaves linked through the Root node. |
Methods
Add(Position, T)
Declaration
public void Add(Position position, T value)
Parameters
Type |
Name |
Description |
Position |
position |
A Position with respective coordinate, geospatial or not |
T |
value |
The value to be inserted |
Add(Double[], T)
Inserts a value in the tree at the desired position.
Declaration
public void Add(double[] position, T value)
Parameters
Type |
Name |
Description |
System.Double[] |
position |
A double-vector with the same number of elements as dimensions in the tree. |
T |
value |
The value to be inserted. |
Create(Double[][], T[], Int32, Int32, Int32, Int32, ElementComparer, ref Int32)
Creates a new
KdTree<T> from given
and associated
.
Declaration
protected static KdTreeNode<T> Create(double[][] points, T[] values, int depth, int k, int start, int length, ElementComparer comparer, ref int leaves)
Parameters
Type |
Name |
Description |
System.Double[][] |
points |
|
T[] |
values |
|
System.Int32 |
depth |
|
System.Int32 |
k |
|
System.Int32 |
start |
|
System.Int32 |
length |
|
ElementComparer |
comparer |
|
System.Int32 |
leaves |
|
Returns
Type |
Description |
KdTreeNode<T> |
Returns a new KdTree<T> filled by given
and associated to respective .
|
Implements
System.Collections.Generic.IEnumerable<T>
System.Collections.IEnumerable
Extension Methods