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.
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.Gemometry 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.
"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.