Class: Aims::KDTree

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

Overview

Courtesy of gist.github.com/cbrumelle/328423

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(points, dim) ⇒ KDTree

Returns a new instance of KDTree.



7
8
9
10
 
# File 'lib/aims/kd_tree.rb', line 7

def initialize(points, dim)
  @dim = dim
  @root = KDNode.new(dim).parse(points)
end

Instance Attribute Details

#points ⇒ Object (readonly)

Returns the value of attribute points.



5
6
7
 
# File 'lib/aims/kd_tree.rb', line 5

def points
  @points
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



4
5
6
 
# File 'lib/aims/kd_tree.rb', line 4

def root
  @root
end

Instance Method Details

#add_node(point) ⇒ Object 



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

def add_node(point)
  @root.add(point)
end

#find(*range) ⇒ Object 



16
17
18
19
20
21
22
23
 
# File 'lib/aims/kd_tree.rb', line 16

def find(*range)
  range.collect!{ |pa|
    pa = Range.new(pa.first, pa.last) if pa.kind_of? Array
  }
  @points = []
  query(range, @root)
  @points
end

#print ⇒ Object 



42
43
44
 
# File 'lib/aims/kd_tree.rb', line 42

def print
  @root.print
end

#query(range, node) ⇒ Object 



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/aims/kd_tree.rb', line 25

def query(range, node)
  axis = node.axis
  median = node.location[axis]
 
  if node.left && (median >= range[axis].begin)
    query(range, node.left);  # /* Skip left if max of left tree (median) is out of range */
  end
  if node.right && (median <= range[axis].end)
    query(range, node.right); # /* Skip right if min of right tree (median) is out of range */
  end
  if (0..@dim-1).all?{|ax|
      range[ax].include? node.location[ax]
    }
    @points << node.location;
  end
end