Class: Containers::KDTree

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

Overview

A kd-tree allows searching of points in multi-dimensional space, increasing

efficiency for nearest-neighbor searching in particular.

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize(points) ⇒ KDTree 



11
12
13
14
 
# File 'lib/containers/kd_tree.rb', line 11

def initialize(points)
  @root = build_tree(points)
  @nearest = []
end

Instance Method Details

#check_nearest(nearest, node, target, k_nearest) ⇒ Object

Update array of nearest elements if necessary



42
43
44
45
46
47
48
49
50
 
# File 'lib/containers/kd_tree.rb', line 42

def check_nearest(nearest, node, target, k_nearest)
  d = distance2(node, target) 
  if nearest.size < k_nearest || d < nearest.last[0]
    nearest.pop if nearest.size >= k_nearest
    nearest << [d, node.id]
    nearest.sort! { |a, b| a[0] <=> b[0] }
  end
  nearest
end

#find_nearest(target, k_nearest) ⇒ Object

Find k closest points to given coordinates



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

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