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 



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

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 



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'app/services/rectangle_packer.rb', line 60

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 



92
93
94
95
96
97
98
99
100
101
102
 
# File 'app/services/rectangle_packer.rb', line 92

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 



80
81
82
83
84
85
86
87
88
89
90
 
# File 'app/services/rectangle_packer.rb', line 80

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 = {}) ⇒ Hash

Packs rectangles into the smallest containing rectangle.

Parameters:

  • rectangles (Array<Hash>) —

    rectangles with :length and :width keys

  • options (Hash) (defaults to: {}) —

    configurable options

Options Hash (options):

  • wpadding (Numeric) —

    horizontal padding added around each rectangle

  • vpadding (Numeric) —

    vertical padding added around each rectangle

  • wmargin (Numeric) —

    horizontal margin added around each rectangle

  • vmargin (Numeric) —

    vertical margin added around each rectangle

Returns:

  • (Hash) —

    packed dimensions with :length and :width keys



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
37
38
39
40
41
42
43
44
 
# File 'app/services/rectangle_packer.rb', line 12

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 



54
55
56
57
58
 
# File 'app/services/rectangle_packer.rb', line 54

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