Class: Containers::KDTree

Inherits:
Object
  • Object
show all
Defined in:
lib/containers/kd_tree.rb

Overview

rdoc

A kd-tree is a binary tree that allows one to store points (of any space dimension: 2D, 3D, etc).
The structure of the resulting tree makes it so that large portions of the tree are pruned
during queries.

One very good use of the tree is to allow nearest neighbor searching. Let's say you have a number
of points in 2D space, and you want to find the nearest 2 points from a specific point:

First, put the points into the tree:

  kdtree = Containers::KDTree.new( {0 => [4, 3], 1 => [3, 4], 2 => [-1, 2], 3 => [6, 4],
                                   4 => [3, -5], 5 => [-2, -5] })

Then, query on the tree:

  puts kd.find_nearest([0, 0], 2) => [[5, 2], [9, 1]]

The result is an array of [distance, id] pairs. There seems to be a bug in this version.

Note that the point queried on does not have to exist in the tree. However, if it does exist,
it will be returned.

MIT License

Copyright (c) 2009 Kanwei Li

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize(points) ⇒ KDTree

Points is a hash of id => [coord, coord] pairs.



51
52
53
54
55
56
 
# File 'lib/containers/kd_tree.rb', line 51

def initialize(points)
  raise "must pass in a hash" unless points.kind_of?(Hash)
  @dimensions = points[ points.keys.first ].size
  @root = build_tree(points.to_a)
  @nearest = []
end

Instance Method Details

#find_nearest(target, k_nearest) ⇒ Object

Find k closest points to given coordinates



59
60
61
62
 
# File 'lib/containers/kd_tree.rb', line 59

def find_nearest(target, k_nearest)
  @nearest = []
  nearest(@root, target, k_nearest, 0)
end