Class: KDTree

Inherits:
Object
  • Object
show all
Defined in:
lib/kd_tree.rb,
lib/kd_tree/point.rb,
lib/kd_tree/hyper_rect.rb

Defined Under Namespace

Classes: HyperRect, Point

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(exemplar_set) ⇒ KDTree

Returns a new instance of KDTree.



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

def initialize(exemplar_set)
  return if exemplar_set.empty?
  exemplar_set = extract_pivot exemplar_set
  split! exemplar_set
end

Instance Attribute Details

#exemplar ⇒ Object

Returns the value of attribute exemplar.



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

def exemplar
  @exemplar
end

#kd_left ⇒ Object

Returns the value of attribute kd_left.



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

def kd_left
  @kd_left
end

#kd_right ⇒ Object

Returns the value of attribute kd_right.



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

def kd_right
  @kd_right
end

#split ⇒ Object

Returns the value of attribute split.



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

def split
  @split
end

Instance Method Details

#backtrack_check(target, n, metric, acc, hr, max_dist, kd) ⇒ Object 



84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/kd_tree.rb', line 84

def backtrack_check(target, n, metric, acc, hr, max_dist, kd)
  if hr.intersects? target, max_dist, metric
    dist = @exemplar.distance_from(target, metric)
    if acc.length < n || dist < acc.last[:dist]
      acc = acc.clone
      max_dist = dist if acc.length == n
      acc << {:node => @exemplar, :dist => dist}
      acc = acc.sort_by { |node| node[:dist] }
      acc.delete_at n if acc.length > n
    end
    temp_acc = kd.nearest_neighbors target, n, metric, acc, hr, max_dist
    if ((temp_acc.length > 0) && (acc.length < n || temp_acc.last[:dist] < acc.last[:dist]))
      acc = temp_acc
    end
  end
  acc
end

#cut_kspace_by(target, hr) ⇒ Object 



66
67
68
69
70
71
72
73
 
# File 'lib/kd_tree.rb', line 66

def cut_kspace_by(target, hr)
  hrl, hrr = hr.cut @split, @exemplar[@split]
  if target[@split] <= @exemplar[@split]
    [@kd_left, hrl, @kd_right, hrr]
  else
    [@kd_right, hrr, @kd_left, hrl]
  end
end

#extract_pivot(exemplar_set) ⇒ Object 



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/kd_tree.rb', line 13

def extract_pivot(exemplar_set)
  k = exemplar_set[0].length - 1
  max_spread = -Float::INFINITY
  max_spread_o = 0
  max_spread_d = 0
  k.times do |i|
    min = Float::INFINITY
    max = -Float::INFINITY
    exemplar_set.each do |ex|
      min = ex[k] if ex[k] < min
      max = ex[k] if ex[k] > max
    end
    if max - min > max_spread
      max_spread = max - min
      max_spread_o = min
      max_spread_d = i
    end
  end
  @split = max_spread_d
  mid_coord = max_spread_o + (max_spread/2.0)
  split_d_coords = exemplar_set.map do |ex|
    ex[split]
  end
  mid_closest_coord = Float::INFINITY
  mid_closest_index = 0
  split_d_coords.each_with_index do |coord, i|
    if (coord - mid_coord).abs < mid_closest_coord
      mid_closest_coord = coord
      mid_closest_index = i
    end
  end
  @exemplar = exemplar_set.delete_at mid_closest_index
  exemplar_set
end

#nearest_neighbor(target, metric = :euclidean) ⇒ Object 



62
63
64
 
# File 'lib/kd_tree.rb', line 62

def nearest_neighbor(target, metric=:euclidean)
  nearest_neighbors(target, 1, metric)[0]
end

#nearest_neighbors(target, n, metric = :euclidean, acc = [], hr = HyperRect.new(target.length), max_dist = Float::INFINITY) ⇒ Object 



75
76
77
78
79
80
81
82
 
# File 'lib/kd_tree.rb', line 75

def nearest_neighbors(target, n, metric=:euclidean, acc=[], hr=HyperRect.new(target.length), max_dist=Float::INFINITY)
  return acc if @exemplar.nil?
  nearer_kd, nearer_hr, further_kd, further_hr = self.cut_kspace_by target, hr
  acc = nearer_kd.nearest_neighbors target, n, metric, acc, nearer_hr, max_dist
  max_dist = acc.last[:dist] if acc.length == n && acc.last[:dist] < max_dist
  acc = backtrack_check target, n, metric, acc, further_hr, max_dist, further_kd
  acc.sort_by { |node| node[:dist] }
end

#split!(exemplar_set) ⇒ Object 



48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/kd_tree.rb', line 48

def split!(exemplar_set)
  left_set = []
  right_set = []
  exemplar_set.each do |ex|
    if ex[@split] <= @exemplar[@split]
      left_set << ex
    else
      right_set << ex
    end
  end
  @kd_left = self.class.new left_set
  @kd_right = self.class.new right_set
end