Kd-tree
My Ruby implementation of a Kd-tree. Kd-trees allow for fast nearest-neighbor searches. This implementation will also allow the Kd-tree to be cached using Rails.cache methods. For now, this only supports 2d latitude/longitude searches.
Getting Started
Add the gem:
gem 'cacheable_kdtree'Usage
A Kd-tree is made up of multiple nodes. A single node contains the data associated with the latitude/longitude:
CacheableKdtree::LatitudeLongitudeNode.new(your_data_here, latitude_of_your_data, longitude_of_your_data)Once you have an array of nodes, you can create a Kd-tree:
nodes = [CacheableKdtree::LatitudeLongitudeNode.new(...), CacheableKdtree::LatitudeLongitudeNode.new(...)]
my_tree = CacheableKdtree::LatitudeLongitudeTree.new(nodes)You can query your tree and return the closest nodes:
# The 4th parameter may be :miles or :kilometers
all_my_nodes = my_tree.closest(my_lat, my_long, distance, :kilometers)
# You may then sort the nodes by their distance to a point (using the Law of Cosines)
sorted_nodes = CacheableKdtree::LatitudeLongitudeNode.sort_by_distance_between(my_lat, my_long, all_my_nodes)
# To get your filtered, sorted data, you may run:
my_data_list = sorted_nodes.map(:&data)Contributing
Bug reports and pull requests are welcome on GitHub at https://github.com/aaronFranssell/cacheable_kdtree.
Please make sure all tests pass and that Rubocop is happy:
rake test
rubocop -Dac .rubocop.yml