Class KdTree<T>

An implementation of a KD - Tree over two dimensions(X and Y). KD-trees provide fast range searching and fast lookup for point data. The tree is built dynamically by inserting points. The tree supports queries by range and for point equality. For querying an internal stack is used instead of recursion to avoid overflow.

Inheritance

object

KdTree<T>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: NetTopologySuite.Index.KdTree

Assembly: NetTopologySuite.dll

Syntax

public class KdTree<T> where T : class

Type Parameters

Name	Description
T	The type of the user data object

Remarks

This implementation supports detecting and snapping points which are closer than a given distance tolerance. If the same point (up to tolerance) is inserted more than once , it is snapped to the existing node. In other words, if a point is inserted which lies within the tolerance of a node already in the index, it is snapped to that node. When an inserted point is snapped to a node then a new node is not created but the count of the existing node is incremented. If more than one node in the tree is within tolerance of an inserted point, the closest and then lowest node is snapped to.

The structure of a KD-Tree depends on the order of insertion of the points. A tree may become umbalanced if the inserted points are coherent (e.g.monotonic in one or both dimensions). A perfectly balanced tree has depth of only log2(N), but an umbalanced tree may be much deeper. This has a serious impact on query efficiency. One solution to this is to randomize the order of points before insertion (e.g. by using Fisher - Yates shuffling).

Constructors

KdTree()

Creates a new instance of a KdTree with a snapping tolerance of 0.0. (I.e. distinct points will not be snapped)

Declaration

public KdTree()

KdTree(double)

Creates a new instance of a KdTree with a snapping distance tolerance. Points which lie closer than the tolerance to a point already in the tree will be treated as identical to the existing point.

Declaration

public KdTree(double tolerance)

Parameters

Type	Name	Description
double	tolerance	The tolerance distance for considering two points equal

Properties

Count

Gets a value indicating the number of items in the tree.

Declaration

public int Count { get; }

Property Value

Type	Description
int	The number of items in the tree.

Depth

Gets a value indicating the depth of the tree

Declaration

public int Depth { get; }

Property Value

Type	Description
int	The depth of the tree

IsEmpty

Tests whether the index contains any items.

Declaration

public bool IsEmpty { get; }

Property Value

Type	Description
bool

Root

Gets a value indicating the root node of the tree

Declaration

public KdNode<T> Root { get; }

Property Value

Type	Description
KdNode<T>	The root node of the tree

Methods

Insert(Coordinate)

Inserts a new point in the kd-tree, with no data.

Declaration

public KdNode<T> Insert(Coordinate p)

Parameters

Type	Name	Description
Coordinate	p	The point to insert

Returns

Type	Description
KdNode<T>	The kdnode containing the point

Insert(Coordinate, T)

Inserts a new point into the kd-tree.

Declaration

public KdNode<T> Insert(Coordinate p, T data)

Parameters

Type	Name	Description
Coordinate	p	The point to insert
T	data	A data item for the point

Returns

Type	Description
KdNode<T>	A new KdNode if a new point is inserted, else an existing node is returned with its counter incremented. This can be checked by testing returnedNode.getCount() > 1.

InsertExact(Coordinate, T)

Inserts a point known to be beyond the distance tolerance of any existing node. The point is inserted at the bottom of the exact splitting path, so that tree shape is deterministic.

Declaration

public KdNode<T> InsertExact(Coordinate p, T data)

Parameters

Type	Name	Description
Coordinate	p	The point to insert
T	data	The data associated with p

Returns

Type	Description
KdNode<T>	The data for the point The created node

Query(Coordinate)

Searches for a given point in the index and returns its node if found.

Declaration

public KdNode<T> Query(Coordinate queryPt)

Parameters

Type	Name	Description
Coordinate	queryPt	the point to query

Returns

Type	Description
KdNode<T>	the point node, if it is found in the index, or null if not

Query(Envelope)

Performs a range search of the points in the index.

Declaration

public IList<KdNode<T>> Query(Envelope queryEnv)

Parameters

Type	Name	Description
Envelope	queryEnv	The range rectangle to query

Returns

Type	Description
IList<KdNode<T>>	A collection of the KdNodes found

Query(Envelope, IKdNodeVisitor<T>)

Performs a range search of the points in the index and visits all nodes found.

Declaration

public void Query(Envelope queryEnv, IKdNodeVisitor<T> visitor)

Parameters

Type	Name	Description
Envelope	queryEnv	The range rectangle to query
IKdNodeVisitor<T>	visitor	A visitor to visit all nodes found by the search

Query(Envelope, IList<KdNode<T>>)

Performs a range search of the points in the index.

Declaration

public void Query(Envelope queryEnv, IList<KdNode<T>> result)

Parameters

Type	Name	Description
Envelope	queryEnv	The range rectangle to query
IList<KdNode<T>>	result	A collection to accumulate the result nodes into

ToCoordinates(IEnumerable<KdNode<T>>)

Converts a collection ofKdNode<T> s to an array of Coordinates.

Declaration

public static Coordinate[] ToCoordinates(IEnumerable<KdNode<T>> kdnodes)

Parameters

Type	Name	Description
IEnumerable<KdNode<T>>	kdnodes	A collection of nodes

Returns

Type	Description
Coordinate[]	An array of the coordinates represented by the nodes

ToCoordinates(IEnumerable<KdNode<T>>, bool)

Converts a collection of KdNode<T>{@link KdNode}s to an array of Coordinates, specifying whether repeated nodes should be represented by multiple coordinates.

Declaration

public static Coordinate[] ToCoordinates(IEnumerable<KdNode<T>> kdnodes, bool includeRepeated)

Parameters

Type	Name	Description
IEnumerable<KdNode<T>>	kdnodes	a collection of nodes
bool	includeRepeated	true if repeated nodes should be included multiple times

Returns

Type	Description
Coordinate[]	An array of the coordinates represented by the nodes

Extension Methods

KdTreeExtensions.NearestNeighbor<T>(KdTree<T>, Coordinate)