Class KdTreeBase<TNode>

Base class for K-dimensional trees.

Inheritance

System.Object

Mars.Common.Core.Collections.SimpleTree.BinaryTree<TNode>

KdTreeBase<TNode>

K2DTree<T>

KdTree

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 Source

KdTreeBase(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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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 Source

Count

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

| Improve this Doc View Source

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

| Improve this Doc View Source

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[]>

| Improve this Doc View Source

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 Source

AddNode(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

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

Clear()

Removes all nodes from this tree.

Declaration

public void Clear()

| Improve this Doc View Source

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.

| Improve this Doc View Source

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`.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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.

| Improve this Doc View Source

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

| Improve this Doc View Source

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

| Improve this Doc View Source

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)