Class: RectanglePacker

Inherits:
Object
  • Object
show all
Defined in:
app/services/rectangle_packer.rb

Instance Method Summary collapse

Instance Method Details

#find_node(root, l, w) ⇒ Object 



38
39
40
41
42
43
44
 
# File 'app/services/rectangle_packer.rb', line 38

def find_node(root, l, w)
  if root[:used]
    find_node(root[:right], l, w) || find_node(root[:down], l, w)
  elsif (l <= root[:l]) && (w <= root[:w])
    root
  end
end

#grow(root, l, w) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'app/services/rectangle_packer.rb', line 52

def grow(root, l, w)

  cangrow_down  = (l <= root[:l])
  cangrow_right = (w <= root[:w])

  shouldgrow_right = cangrow_right && (root[:w] >= (root[:l] + l))
  shouldgrow_down  = cangrow_down  && (root[:l] >= (root[:w] + w))

  if shouldgrow_right
    grow_right(root, l, w)
  elsif shouldgrow_down
    grow_down(root, l, w)
  elsif cangrow_right
    grow_right(root, l, w)
  elsif cangrow_down
    grow_down(root, l, w)
  else
    raise RuntimeError, "can't fit #{l}x#{w} block into root #{root[:l]}x#{root[:w]} - this should not happen if images are pre-sorted correctly"
  end

end

#grow_down(root, l, w) ⇒ Object 



86
87
88
89
90
91
92
93
94
95
96
 
# File 'app/services/rectangle_packer.rb', line 86

def grow_down(root, l, w)
  return {
    :used  => true,
    :x     => 0,
    :y     => 0,
    :l     => root[:l],
    :w     => root[:w] + w,
    :down  => { :x => 0, :y => root[:w], :l => root[:l], :w => w },
    :right => root
  }
end

#grow_right(root, l, w) ⇒ Object 



74
75
76
77
78
79
80
81
82
83
84
 
# File 'app/services/rectangle_packer.rb', line 74

def grow_right(root, l, w)
  return {
    :used  => true,
    :x     => 0,
    :y     => 0,
    :l     => root[:l] + l,
    :w     => root[:w],
    :down  => root,
    :right => { :x => root[:l], :y => 0, :l => l, :w => root[:w] }
  }
end

#process(rectangles, options = {}) ⇒ Object 



3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'app/services/rectangle_packer.rb', line 3

def process(rectangles, options={})
  hpadding = options[:wpadding] || 0
  vpadding = options[:vpadding] || 0
  hmargin  = options[:wmargin]  || 0
  vmargin  = options[:vmargin]  || 0
  return { :length => 0, :width => 0 } if rectangles.empty?

  rectangles.each do |r|
    r[:l] = r[:length]  + (2*hpadding) + (2*hmargin)
    r[:w] = r[:width] + (2*vpadding) + (2*vmargin)
  end

  rectangles.sort! do |a,b|
    diff = [b[:l], b[:w]].max <=> [a[:l], a[:w]].max
    diff = [b[:l], b[:w]].min <=> [a[:l], a[:w]].min if diff.zero?
    diff = b[:w] <=> a[:w] if diff.zero?
    diff = b[:l]  <=> a[:l]  if diff.zero?
    diff
  end

  root = { :x => 0, :y => 0, :l => rectangles[0][:l], :w => rectangles[0][:w] }

  rectangles.each do |r|
    if (node = find_node(root, r[:l], r[:w]))
      split_node(node, r[:l], r[:w])
    else
      root = grow(root, r[:l], r[:w])
      redo
    end
  end

  { :length => root[:l], :width => root[:w] }

end

#split_node(node, l, w) ⇒ Object 



46
47
48
49
50
 
# File 'app/services/rectangle_packer.rb', line 46

def split_node(node, l, w)
  node[:used]  = true
  node[:down]  = { :x => node[:x],     :y => node[:y] + w, :l => node[:l],     :w => node[:w] - w }
  node[:right] = { :x => node[:x] + l, :y => node[:y],     :l => node[:l] - l, :w => w            }
end