Class: Aims::KDNode

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(dim, location = nil, left = nil, right = nil) ⇒ KDNode

Returns a new instance of KDNode.



53
54
55
56
57
58
 
# File 'lib/aims/kd_tree.rb', line 53

def initialize(dim, location=nil, left=nil, right=nil)
  @dim = dim
  @location = location
  @left = left
  @right = right
end

Instance Attribute Details

#axis ⇒ Object (readonly)

Returns the value of attribute axis.



51
52
53
 
# File 'lib/aims/kd_tree.rb', line 51

def axis
  @axis
end

#left ⇒ Object (readonly)

Returns the value of attribute left.



48
49
50
 
# File 'lib/aims/kd_tree.rb', line 48

def left
  @left
end

#location ⇒ Object (readonly)

Returns the value of attribute location.



49
50
51
 
# File 'lib/aims/kd_tree.rb', line 49

def location
  @location
end

#right ⇒ Object (readonly)

Returns the value of attribute right.



48
49
50
 
# File 'lib/aims/kd_tree.rb', line 48

def right
  @right
end

Instance Method Details

#add(point) ⇒ Object 



72
73
74
75
76
77
78
 
# File 'lib/aims/kd_tree.rb', line 72

def add(point)
  if @location[@axis] < point[@axis]
    @left ? @left.add(point) : @left = KDNode.new(point)
  else
    @right ? @right.add(point) : @right = KDNode.new(point)
  end
end

#parse(points, depth = 0) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/aims/kd_tree.rb', line 60

def parse(points, depth = 0)
  @axis = depth % @dim
 
  points = points.sort_by{|point| point[@axis]}
  half = points.length / 2
 
  @location = points[half]
  @left = KDNode.new(@dim).parse(points[0..half-1], depth+1) unless half < 1
  @right = KDNode.new(@dim).parse(points[half+1..-1], depth+1) unless half+1 >= points.length
  self
end

#print(l = 0) ⇒ Object 



88
89
90
91
92
 
# File 'lib/aims/kd_tree.rb', line 88

def print(l=0)
  @left.print(l+1) if @left
  puts("  "*l + @location.inspect)
  @right.print(l+1) if @right
end

#remove ⇒ Object 



80
81
82
 
# File 'lib/aims/kd_tree.rb', line 80

def remove
  self.parse(@left.to_a + @right.to_a, @axis)
end

#to_a ⇒ Object 



84
85
86
 
# File 'lib/aims/kd_tree.rb', line 84

def to_a
  @left.to_a + [@location] + @right.to_a
end