Class KdTreeBase<TNode>
Base class for K-dimensional trees.
Inheritance
System.Object
Mars.Common.Core.Collections.SimpleTree.BinaryTree<TNode>
KdTreeBase<TNode>
KdTree<T>
Implements
System.Collections.Generic.IEnumerable<TNode>
System.Collections.IEnumerable
Inherited Members
Mars.Common.Core.Collections.SimpleTree.BinaryTree<TNode>.Root
Mars.Common.Core.Collections.SimpleTree.BinaryTree<TNode>.GetEnumerator()
Mars.Common.Core.Collections.SimpleTree.BinaryTree<TNode>.System.Collections.IEnumerable.GetEnumerator()
Mars.Common.Core.Collections.SimpleTree.BinaryTree<TNode>.SerializeJson()
Mars.Common.Core.Collections.SimpleTree.BinaryTree<TNode>.Deserialize(System.String)
Mars.Common.Core.Collections.SimpleTree.BinaryTree<TNode>.Traverse(Mars.Common.Core.Collections.SimpleTree.BinaryTraversalMethod<TNode>)
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()
Namespace: Mars.Common.Collections
Assembly: Mars.Common.dll
Syntax
[Serializable]
public abstract class KdTreeBase<TNode> : BinaryTree<TNode>, IEnumerable<TNode>, IEnumerable where TNode : KdTreeNodeBase<TNode>, IComparable<TNode>, new()
Type Parameters
Name | Description |
---|---|
TNode | The class type for the nodes of the tree. |
Constructors
| Improve this Doc View SourceKdTreeBase(Int32, TNode, Int32, Int32)
Creates a new KdTree<T>.
Declaration
public KdTreeBase(int dimension, TNode root, int count, int leaves)
Parameters
Type | Name | Description |
---|---|---|
System.Int32 | dimension | The number of dimensions in the tree. |
TNode | 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. |
KdTreeBase(Int32, TNode)
Creates a new KdTree<T>.
Declaration
public KdTreeBase(int dimension, TNode root)
Parameters
Type | Name | Description |
---|---|---|
System.Int32 | dimension | The number of dimensions in the tree. |
TNode | root | The Root node, if already existent. |
KdTreeBase(Int32)
Creates a new KdTree<T>.
Declaration
public KdTreeBase(int dimensions)
Parameters
Type | Name | Description |
---|---|---|
System.Int32 | dimensions | The number of dimensions in the tree. |
Properties
| Improve this Doc View SourceCount
Gets the number of elements contained in this
tree. This is also the number of tree nodes.
Declaration
[JsonProperty("count")]
public int Count { get; }
Property Value
Type | Description |
---|---|
System.Int32 |
Dimensions
Gets the number of dimensions expected
by the input points of this tree.
Declaration
[JsonProperty("dimensions")]
public int Dimensions { get; }
Property Value
Type | Description |
---|---|
System.Int32 |
Distance
Gets or set the distance function used to
measure distances amongst points on this tree
Declaration
public IMetric<double[]> Distance { get; set; }
Property Value
Type | Description |
---|---|
IMetric<System.Double[]> |
Leaves
Gets the number of leaves contained in this
tree. This can be used to calibrate approximate
nearest searchers.
Declaration
[JsonProperty("leaves")]
public int Leaves { get; }
Property Value
Type | Description |
---|---|
System.Int32 |
Methods
| Improve this Doc View SourceAddNode(Double[])
Inserts a value into the tree at the desired position.
Declaration
protected TNode AddNode(double[] position)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | A double-vector with the same number of elements as dimensions in the tree. |
Returns
Type | Description |
---|---|
TNode |
ApproximateNearest(Double[], Double, out Double)
Retrieves a percentage of nearest points to a given point.
Declaration
public TNode ApproximateNearest(double[] position, double percentage, out double distance)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Double | percentage | The maximum percentage of leaf nodes that can be visited before the search finishes with an approximate answer. |
System.Double | distance | The distance between the query point and its nearest neighbor. |
Returns
Type | Description |
---|---|
TNode | A list of neighbor points, ordered by distance. |
ApproximateNearest(Double[], Double)
Retrieves a percentage of nearest points to a given point.
Declaration
public TNode ApproximateNearest(double[] position, double percentage)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Double | percentage | The maximum percentage of leaf nodes that can be visited before the search finishes with an approximate answer. |
Returns
Type | Description |
---|---|
TNode | A list of neighbor points, ordered by distance. |
ApproximateNearest(Double[], Int32, Double)
Retrieves a fixed percentage of nearest points to a given point.
Declaration
public KdTreeNodeCollection<TNode> ApproximateNearest(double[] position, int neighbors, double percentage)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Int32 | neighbors | The number of neighbors to retrieve. |
System.Double | percentage | The maximum percentage of leaf nodes that can be visited before the search finishes with an approximate answer. |
Returns
Type | Description |
---|---|
KdTreeNodeCollection<TNode> | A list of neighbor points, ordered by distance. |
ApproximateNearest(Double[], Int32, Int32)
Retrieves a fixed number of nearest points to a given point.
Declaration
public KdTreeNodeCollection<TNode> ApproximateNearest(double[] position, int neighbors, int maxLeaves)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Int32 | neighbors | The number of neighbors to retrieve. |
System.Int32 | maxLeaves | The maximum number of leaf nodes that can be visited before the search finishes with an approximate answer. |
Returns
Type | Description |
---|---|
KdTreeNodeCollection<TNode> | A list of neighbor points, ordered by distance. |
ApproximateNearest(Double[], Int32)
Retrieves a fixed number of nearest points to a given point.
Declaration
public TNode ApproximateNearest(double[] position, int maxLeaves)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Int32 | maxLeaves | The maximum number of leaf nodes that can be visited before the search finishes with an approximate answer. |
Returns
Type | Description |
---|---|
TNode | A list of neighbor points, ordered by distance. |
Clear()
Removes all nodes from this tree.
Declaration
public void Clear()
CopyTo(TNode[], Int32)
Copies the entire tree to a compatible one-dimensional System.Array, starting
at the specified
arrayIndex
of the
array
.
Declaration
public void CopyTo(TNode[] array, int arrayIndex)
Parameters
Type | Name | Description |
---|---|---|
TNode[] | array | The one-dimensional System.Array that is the destination of the elements copied from tree. The System.Array must have zero-based indexing. |
System.Int32 | arrayIndex | The zero-based index in array at which copying begins. |
CreateRoot(Double[][], Boolean, out Int32)
Creates the Root node for a new KdTree<T> given
a set of data points and their respective stored values.
Declaration
protected static TNode CreateRoot(double[][] points, bool inPlace, out int leaves)
Parameters
Type | Name | Description |
---|---|---|
System.Double[][] | points | The data points to be inserted in the tree. |
System.Boolean | inPlace |
Whether the given points vector
can be ordered in place. Passing true will change the original order of
the vector. If set to false, all operations will be performed on an extra
copy of the vector.
|
System.Int32 | leaves | Return the number of leaves in the Root subtree. |
Returns
Type | Description |
---|---|
TNode |
The Root node for a new KdTree<T>
contained the given points .
|
InsideRegion(Hyperrectangle)
Retrieves a list of all points inside a given region.
Declaration
public IList<TNode> InsideRegion(Hyperrectangle region)
Parameters
Type | Name | Description |
---|---|---|
Hyperrectangle | region | The region. |
Returns
Type | Description |
---|---|
System.Collections.Generic.IList<TNode> | A list of all nodes contained in the region. |
Nearest(Position, Double, Int32, Func<TNode, Boolean>)
Retrieves the nearest points to a given Position within a given radius.
Declaration
public ICollection<NodeDistance<TNode>> Nearest(Position position, double radius, int maximum, Func<TNode, bool> predicate = null)
Parameters
Type | Name | Description |
---|---|---|
Position | position | The queried Position. |
System.Double | radius | The search radius. |
System.Int32 | maximum | The maximum number of neighbors to retrieve. |
System.Func<TNode, System.Boolean> | predicate | The predicate to filter out the nodes. |
Returns
Type | Description |
---|---|
System.Collections.Generic.ICollection<NodeDistance<TNode>> | A list of neighbor points, ordered by distance. |
Nearest(Double[], Double, Func<TNode, Boolean>)
Retrieves the nearest points to a given point within a given radius.
Declaration
public List<NodeDistance<TNode>> Nearest(double[] position, double radius, Func<TNode, bool> predicate = null)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Double | radius | The search radius. |
System.Func<TNode, System.Boolean> | predicate | The predicate to filter out the nodes. |
Returns
Type | Description |
---|---|
System.Collections.Generic.List<NodeDistance<TNode>> | A list of neighbor points, ordered by distance. |
Nearest(Double[], Double, Int32, Func<TNode, Boolean>)
Retrieves the nearest points to a given point within a given radius.
Declaration
public ICollection<NodeDistance<TNode>> Nearest(double[] position, double radius, int maximum, Func<TNode, bool> predicate = null)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Double | radius | The search radius. |
System.Int32 | maximum | The maximum number of neighbors to retrieve. |
System.Func<TNode, System.Boolean> | predicate | The predicate to filter out the nodes. |
Returns
Type | Description |
---|---|
System.Collections.Generic.ICollection<NodeDistance<TNode>> | A list of neighbor points, ordered by distance. |
Nearest(Double[], out Double, Func<TNode, Boolean>)
Retrieves the nearest point to a given point.
Declaration
public TNode Nearest(double[] position, out double distance, Func<TNode, bool> predicate = null)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Double | distance |
The distance from the position
to its nearest neighbor found in the tree.
|
System.Func<TNode, System.Boolean> | predicate | The predicate to filter out the nodes. |
Returns
Type | Description |
---|---|
TNode | A list of neighbor points, ordered by distance. |
Nearest(Double[], Int32, Func<TNode, Boolean>)
Retrieves a fixed number of nearest points to a given point.
Declaration
public KdTreeNodeCollection<TNode> Nearest(double[] position, int neighbors, Func<TNode, bool> predicate = null)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
System.Int32 | neighbors | The number of neighbors to retrieve. |
System.Func<TNode, System.Boolean> | predicate | The predicate to filter out the nodes. |
Returns
Type | Description |
---|---|
KdTreeNodeCollection<TNode> | A list of neighbor points, ordered by distance. |
Nearest(Double[])
Retrieves the nearest point to a given point.
Declaration
public TNode Nearest(double[] position)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | The queried point. |
Returns
Type | Description |
---|---|
TNode | A list of neighbor points, ordered by distance. |
Nearest<T1>(Double[], Double, Int32, Func<TNode, T1, Boolean>, T1)
Base class for K-dimensional trees.
Declaration
public ICollection<NodeDistance<TNode>> Nearest<T1>(double[] position, double radius, int maximum, Func<TNode, T1, bool> predicate = null, T1 t1 = null)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | |
System.Double | radius | |
System.Int32 | maximum | |
System.Func<TNode, T1, System.Boolean> | predicate | |
T1 | t1 |
Returns
Type | Description |
---|---|
System.Collections.Generic.ICollection<NodeDistance<TNode>> |
Type Parameters
Name | Description |
---|---|
T1 |
Nearest<T1, T2>(Double[], Double, Int32, Func<TNode, T1, T2, Boolean>, T1, T2)
Base class for K-dimensional trees.
Declaration
public ICollection<NodeDistance<TNode>> Nearest<T1, T2>(double[] position, double radius, int maximum, Func<TNode, T1, T2, bool> predicate = null, T1 t1 = null, T2 t2 = null)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | |
System.Double | radius | |
System.Int32 | maximum | |
System.Func<TNode, T1, T2, System.Boolean> | predicate | |
T1 | t1 | |
T2 | t2 |
Returns
Type | Description |
---|---|
System.Collections.Generic.ICollection<NodeDistance<TNode>> |
Type Parameters
Name | Description |
---|---|
T1 | |
T2 |
Nearest<T1, T2, T3>(Double[], Double, Int32, Func<TNode, T1, T2, T3, Boolean>, T1, T2, T3)
Base class for K-dimensional trees.
Declaration
public ICollection<NodeDistance<TNode>> Nearest<T1, T2, T3>(double[] position, double radius, int maximum, Func<TNode, T1, T2, T3, bool> predicate = null, T1 t1 = null, T2 t2 = null, T3 t3 = null)
Parameters
Type | Name | Description |
---|---|---|
System.Double[] | position | |
System.Double | radius | |
System.Int32 | maximum | |
System.Func<TNode, T1, T2, T3, System.Boolean> | predicate | |
T1 | t1 | |
T2 | t2 | |
T3 | t3 |
Returns
Type | Description |
---|---|
System.Collections.Generic.ICollection<NodeDistance<TNode>> |
Type Parameters
Name | Description |
---|---|
T1 | |
T2 | |
T3 |
Implements
System.Collections.Generic.IEnumerable<T>
System.Collections.IEnumerable