Class: ZoneToFit

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

Overview

This is a 2D fit-first greedy heuristic algorithm that tries to fit each box into the trunk, largest first. If no box fits,
a new trunk is created.

I'm representing trunks as 2D tables of squares (with one unit of hidden padding around), then fill it starting
from top left. The fitter-first finds a row with enough empty space to fit the box and then checks if the next box-height
rows also contain the space. If they do, the box is drawn to the rows.
Printing is easy because the trunk already is in printable format.
Not a particularly fast way to do it, mind you :)

If you're interested about different algorithms for solving the 2D bin packing problem,
here's a paper:http://www.dei.unipd.it/~fisch/ricop/tesi/tesi_dottorato_Lodi_1999.pdf

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(w, h) ⇒ ZoneToFit

Returns a new instance of ZoneToFit.



18
19
20
21
22
23
24
25
26
 
# File 'lib/zone_to_fit.rb', line 18

def initialize(w,h)

  @w = w
  @h = h
  @items = []
  @coordinates = []
  @rows = (1..@h).map{ "_"*(@w) }

end

Instance Attribute Details

#coordinates ⇒ Object (readonly)

Returns the value of attribute coordinates.



17
18
19
 
# File 'lib/zone_to_fit.rb', line 17

def coordinates
  @coordinates
end

#items ⇒ Object (readonly)

Returns the value of attribute items.



17
18
19
 
# File 'lib/zone_to_fit.rb', line 17

def items
  @items
end

Instance Method Details

#add(mat) ⇒ Object

try adding the mat both ways, if either fits we assume its now
in the Zone and it will be deleted from the list of mats



30
31
32
33
34
 
# File 'lib/zone_to_fit.rb', line 30

def add mat

  try_adding(mat) or try_adding(rotate(mat), rotated=true)

end

#empty? ⇒ Boolean

simple... trunk has no items in it

Returns:

  • (Boolean) 


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

def empty?

  @items.empty?

end

#fit_mats(mats) ⇒ Object

end to_s



102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/zone_to_fit.rb', line 102

def fit_mats(mats)
  #sort the mats from largest to smallest based on their area (w*h)
  mats = mats.sort_by{|b| b[0]*b[1]}.reverse

  #while there are still mats to try this loop will try to fit them
  #into the zone. We are going through the mats from largest to smallest
  #If a big mat doesn't have room there, all the smaller mats will be tried

  done_filling_zone = false
  until done_filling_zone

    #try to add the mat to the last zone, if it doesn't go we get nil
    fitting = mats.find{|mat| self.add mat }


    #if the mat fit
    if fitting

      #remove the mat from the mats that need to be placed
      #mats.delete_first fitting

    #if the zone is empty
    elsif self.empty?

      #raise an error because the mat is too big to fit into the zone
      #and a solution is impossible
      #puts "Can't fit #{mats.inspect} into the zone"
      return {:items => items, :coordinates => coordinates }

    #mat didn't fit but the zone has mats in it
    else

      done_filling_zone = true

    end #end if fitting

  end #end until

  return {:items => items, :coordinates => coordinates }

end

#rotate(mat) ⇒ Object

end try_adding



83
84
85
 
# File 'lib/zone_to_fit.rb', line 83

def rotate (mat)
  return [mat[1], mat[0], mat[2]]
end

#to_s ⇒ Object

this formatting method is called before the zone is printed.
the extra space is stripped out of the zone here



96
97
98
99
100
 
# File 'lib/zone_to_fit.rb', line 96

def to_s

  @rows[0..@h].map{|r|r[0..@w]}.join("\n")

end

#try_adding(mat, rotated = false) ⇒ Object

end add



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/zone_to_fit.rb', line 36

def try_adding (mat, rotated=false)

  #puts "try adding mat: #{mat.inspect}, index #{mat[2]}"

  #create a new mat row. Also note that matrow
  #is built as a String of "_" characters, so it will be used to find empty Zone space.
  matrow = "_"*(mat[0])

  @rows.each_with_index do |r,i|

    #break out of the loop as soon as we run out of enough @rows to hold the mat (and 2 extra padding @rows)
    break if i > @rows.size - (mat[1])

    #verify that this row holds the mat, or move on
    next unless r.include?(matrow)

    #fetch the index where the mat would fit on @rows needed to hold it below this one
    idxs = @rows[i+1, mat[1]+1].map{|s| s.index matrow }

    #verify that we got an index for all needed lines, or move on.
    next unless idxs.all?

    #find the highest of those indices.
    idx = idxs.max

    #verify that the mat does fit on all needed @rows at the highest found index, or move on
    next unless @rows[i, mat[1]].all?{|s| s[idx,matrow.size] == matrow }

    #if we made it this far, we have a match, so we will draw the mat in place. We can
    #ignore the padding now, since we already proved there is room.
    @rows[i, mat[1]].each{|s| s[idx, mat[0]] = "#{mat[2].first}" * mat[0] }

    #add the mat to the @items, so we know the Zone isn't empty?(), and return the mat to indicate
    #a match
    @items.push mat
    # store coordinate for rendering
    @coordinates.push [idx, i, rotated]
    #puts "mat: #{mat.inspect} did fit"
    return mat

  end #end each_with_index

  #puts "mat: #{mat.inspect} did not fit"
  nil #default false return, if we didn't find a match

end