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