Difference between revisions of "User:Ojd/KD-Tree"
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...") |
(→Files) |
||
| (6 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
== Files == | == Files == | ||
| − | The zip-file contains the whole Visual Studio 2008 solution | + | The zip-file contains the whole Visual Studio 2008 solution including 5 projects: |
<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. | + | <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> | ||
| Line 23: | Line 23: | ||
<li>''Remove'' has three overloads corresponding to the three overloads of ''Add''.</li> | <li>''Remove'' has three overloads corresponding to the three overloads of ''Add''.</li> | ||
<li>''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.</li> | <li>''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.</li> | ||
| + | <li>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.</li> | ||
| + | </ul> | ||
| + | |||
| + | == History == | ||
| + | |||
| + | <ul> | ||
| + | <li>22 May 2012 First version</li> | ||
| + | <li>30 Aug 2013 Minor bugfix</li> | ||
</ul> | </ul> | ||
Latest revision as of 20:30, 13 October 2014
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 including 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.
History
- 22 May 2012 First version
- 30 Aug 2013 Minor bugfix
