Difference between revisions of "User:Ojd/KD-Tree"

From Robowiki
Jump to navigation Jump to search
(Created page with "[http://robowiki.net/wiki/User:Rednaxela Rednaxela] has implemented a nice and efficient [http://robowiki.net/wiki/User:Rednaxela/kD-Tree KD-Tree]. I needed a .NET implementation...")
 
m
Line 7: Line 7:
 
<ul>
 
<ul>
 
<li>'''CySoft.Collections''' contains the different heap-collections used by ''KDTree'' as well as my ''Cache'' and ''MultiMap'' collections not related to ''KDTree''.</li>
 
<li>'''CySoft.Collections''' contains the different heap-collections used by ''KDTree'' as well as my ''Cache'' and ''MultiMap'' collections not related to ''KDTree''.</li>
<li>'''CySoft.Collections.Gemometry''' contains the ''KDTree''.</li>
+
<li>'''CySoft.Collections.Geometry''' contains the ''KDTree''.</li>
 
<li>'''KdTreeTestProject''' contains unit tests (Visual Studio).</li>
 
<li>'''KdTreeTestProject''' contains unit tests (Visual Studio).</li>
 
<li>'''Tests.Benchmark''' contains a simple benchmark console application.</li>
 
<li>'''Tests.Benchmark''' contains a simple benchmark console application.</li>

Revision as of 15:51, 22 May 2012

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.