kd_tree alternatives and similar shards
Based on the "Algorithms and Data structures" category.
Alternatively, view kd_tree alternatives based on common mentions on social networks and blogs.
Do you think we are missing an alternative of kd_tree or a related project?
Crystal implementation of "K-Dimensional Tree" and "N-Nearest Neighbors" based on http://en.wikipedia.org/wiki/Kd-tree.
Add this to your application's
dependencies: kd_tree: github: geocrystal/kd_tree
Construct a new tree. Each point should be of the form
[x, y], where
y are numbers(
kd = Kd::Tree(Int32).new(points)
Find the nearest point to
[x, y]. Returns an array with one point:
Find the nearest
k points to
[x, y]. Returns an array of points:
kd.nearest([x, y], k)
require "kd_tree" points = [ [2.0, 3.0], [5.0, 4.0], [4.0, 7.0], [7.0, 2.0], [8.0, 1.0], [9.0, 6.0], ] kd = Kd::Tree(Float64).new(points) kd.nearest([1.0, 1.0]) # => [[2.0, 3.0]]) kd_tree.nearest([1.0, 1.0], 2) # => [[2.0, 3.0], [5.0, 4.0]])
Using a tree with 1 million points
[x, y] of Float64 on my i7-8550U CPU @ 1.80GHz:
build(init) ~10 seconds nearest point 00.000278579 nearest point 5 00.000693038 nearest point 50 00.007207470 nearest point 255 00.134533902 nearest point 999 08.510465131
- Fork it (https://github.com/geocrystal/kd_tree/fork)
- Create your feature branch (
git checkout -b my-new-feature)
- Commit your changes (
git commit -am 'Add some feature')
- Push to the branch (
git push origin my-new-feature)
- Create a new Pull Request
- mamantoha Anton Maminov - creator, maintainer
*Note that all licence references and agreements mentioned in the kd_tree README section above are relevant to that project's source code only.