Class: RectanglePacker

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

Overview

Service object: rectangle packer.

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
 
# 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 "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 



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

def grow_down(root, _l, w)
  {
    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 



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

def grow_right(root, l, _w)
  {
    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 



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 4

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