User:Ojd/KD-Tree

Rednaxela has implemented a nice and efficient KD-Tree. I needed a .NET implementation and therefore ported his Java implementation to C#. You can find my actual implementation here CySoft.Collections.zip.

Files

The zip-file contains the whole Visual Studio 2008 solution, which includes 5 projects:

• CySoft.Collections contains the different heap-collections used by KDTree as well as my Cache and MultiMap collections not related to KDTree.
• CySoft.Collections.Geometry contains the KDTree.
• KdTreeTestProject contains unit tests (Visual Studio).
• Tests.Benchmark contains a simple benchmark console application.
• Tests.Console is a simple console application displaying some visual tests for the different distance functions.

Description

"A k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space." Wikipedia.

My implementation adds some new functionality to the original implementation.

• It implements ICollection<KDEntry<T>>. System.Collections.Generic.ICollection<T> requires the following methods, Add(), Clear(), Contains(T), CopyTo(T[], int) and Remove(T). It also requires the implementation of IEnumerable<T>.
• There are three overloads of the Add method: 1) Add a value and coordinates, where the coordinates have a params keyword in front of them, which allows you to pass a variable number of coordinates without having to create an array of double explicitly. 2) Add a KDEntry<T> containing a value and a point. 3) Add only a value, where the point or the points associated with the value are automatically extracted from the value by a delegate or lambda expression specified in the constructor of KDTree.
• Remove has three overloads corresponding to the three overloads of Add.
• KDTree has a Points as well as a Values property returning collections of these entities. Together with the implementation of IEnumerable<KDEntry<T>> KDTree provides three very handy ways of iterating through all the entries of the tree.
• To the SquareEuclidianDistance and the ManhattanDistance KDTree adds a ChebyshevDistance which is also known as chess distance. The Chebyshev distance is the maximum distance along any coordinate axis. It corresponds to the number of moves the king needs to reach any position on the chess board.