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.