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:

ruby gem 'cacheable_kdtree'

Usage

A Kd-tree is made up of multiple nodes. A single node contains the data associated with the latitude/longitude:

ruby 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: ruby nodes = [CacheableKdtree::LatitudeLongitudeNode.new(...), CacheableKdtree::LatitudeLongitudeNode.new(...)] my_tree = CacheableKdtree::LatitudeLongitudeTree.new(nodes)

You can query your tree and return the closest nodes: ruby # 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: ruby rake test rubocop -Dac .rubocop.yml