geokdtree

Geokdtree v0.2.0

Ruby & JRuby gem with a fast k-d tree C implementation using FFI bindings with support for latitude/longitude and geo distance range search.

A k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space and are useful for very fast range searches and nearest neighbor searches. k-d trees are a special case of binary space partitioning trees.

Installation

Tested on OSX 10.8.2 and Linux 12.10 with

• MRI Ruby 1.9.3 p362, 1.9.3 p385
• JRuby 1.7.2 (1.9.3 p327)

Add this line to your application's Gemfile:

    gem 'geokdtree'

And then execute:

    $ bundle

Or install it yourself as:

    $ gem install geokdtree

Usage

  # simplest 2d tree
  tree = Geokdtree::Tree.new(2)
  tree.insert([1, 0])
  tree.insert([2, 0])
  tree.insert([3, 0])

  result = tree.nearest([0, 0])
  puts(result.point.inspect) # => [1.0, 0.0]
  puts(result.data.inspect) # => nil

  # simple 2d tree with point payload. 
  # abritary objects can be attached to each inserted point
  tree = Geokdtree::Tree.new(2)
  tree.insert([1, 0], "point 1")
  tree.insert([2, 0], "point 2")
  tree.insert([3, 0], "point 3")

  # single nearest using standard/Euclidean relative distance
  result = tree.nearest([0, 0])
  puts(result.point.inspect) # => [1.0, 0.0]
  puts(result.data.inspect) # => "point 1"

  # nearests within range using standard/Euclidean relative distance
  results = tree.nearest_range([0, 0], 2)
  puts(results.size) # => 2
  puts(results[0].point.inspect) # => [2.0, 0.0]
  puts(results[0].data.inspect) # => "point 2"
  puts(results[1].point.inspect) # => [1.0, 0.0]
  puts(results[1].data.inspect) # => "point 1"

  # 2d tree with lat/lng points
  tree = Geokdtree::Tree.new(2)
  tree.insert([40.7, -74.0], "New York")
  tree.insert([37.77, -122.41], "San Francisco")
  tree.insert([45.50, -73.55], "Montreal")

  # single nearest using standard/Euclidean relative distance
  result = tree.nearest([34.1, -118.2]) # Los Angeles
  puts(result.point.inspect) # => [37.77, -122.41]
  puts(result.data.inspect) # => "San Francisco"


  # nearests within range using miles relative geo distance
  results = tree.nearest_geo_range([47.6, -122.3], 800) # Seattle, within 800 mi
  puts(results.size) # => 1
  puts(results[0].point.inspect) # => [37.77, -122.41]
  puts(results[0].data.inspect) # => "San Francisco"

  # nearests within range using kilometer relative geo distance
  results = tree.nearest_geo_range([42.35, -71.06], 500, :km) # Boston, within 500 km
  puts(results.size) # => 2
  puts(results[0].point.inspect) # => [45.5, -73.55]
  puts(results[0].data.inspect) # => "Montreal"
  puts(results[1].point.inspect) # => [40.7, -74.0]
  puts(results[1].data.inspect) # => "New York"

  # compute standard/Euclidean distance between two points
  d = Geokdtree::Tree.distance([-1, 1], [1, 1])
  puts(d) # => 2

  # compute geo distance between two points (Montreal, Boston)
  d = Geokdtree::Tree.geo_distance([45.5, -73.55], [42.35, -71.06], :km).round(0)
  puts(d.inspect) # => 403

Developement

• Fort it
• Install gems $ bundle install
• Compile lib $ rake compile
• Run specs $ rake spec
• Clean compiler generated files $ rake clean

Contributing

• Fork it
• 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 new Pull Request

Credits

• John Tsiombikas for writing the original C kdtree.

Author

Colin Surprenant, @colinsurprenant, http://github.com/colinsurprenant, [e-mail]

License

Geokdtree is distributed under the Apache License, Version 2.0.