class BinPacking::Bin
Attributes
boxes[R]
height[R]
heuristic[R]
width[R]
Public Class Methods
new(width, height, heuristic = nil)
click to toggle source
# File lib/bin_packing/bin.rb, line 5 def initialize(width, height, heuristic = nil) @width = width @height = height @boxes = [] box = BinPacking::FreeSpaceBox.new(width, height) @free_rectangles = [box] @heuristic = heuristic || BinPacking::Heuristics::BestShortSideFit.new end
Public Instance Methods
efficiency()
click to toggle source
# File lib/bin_packing/bin.rb, line 16 def efficiency boxes_area = 0 @boxes.each { |box| boxes_area += box.area } boxes_area * 100 / area end
insert(box)
click to toggle source
# File lib/bin_packing/bin.rb, line 22 def insert(box) return false if box.packed? @heuristic.find_position_for_new_node!(box, @free_rectangles) return false unless box.packed? insert_in_known_position(box) end
insert!(box)
click to toggle source
# File lib/bin_packing/bin.rb, line 31 def insert!(box) unless insert(box) raise ArgumentError, "Could not insert box #{box.inspect} "\ "into bin #{inspect}." end self end
insert_in_known_position(box)
click to toggle source
# File lib/bin_packing/bin.rb, line 39 def insert_in_known_position(box) num_rectangles_to_process = @free_rectangles.size i = 0 while i < num_rectangles_to_process if split_free_node(@free_rectangles[i], box) @free_rectangles.delete_at(i) num_rectangles_to_process -= 1 else i += 1 end end prune_free_list @boxes << box true end
is_larger_than?(box)
click to toggle source
# File lib/bin_packing/bin.rb, line 61 def is_larger_than?(box) (@width >= box.width && @height >= box.height) || (@height >= box.width && @width >= box.height) end
label()
click to toggle source
# File lib/bin_packing/bin.rb, line 66 def label "#{@width}x#{@height} #{efficiency}%" end
score_for(box)
click to toggle source
# File lib/bin_packing/bin.rb, line 57 def score_for(box) @heuristic.find_position_for_new_node!(box.clone, @free_rectangles) end
Private Instance Methods
area()
click to toggle source
# File lib/bin_packing/bin.rb, line 72 def area @width * @height end
is_contained_in?(rect_a, rect_b)
click to toggle source
# File lib/bin_packing/bin.rb, line 178 def is_contained_in?(rect_a, rect_b) return rect_a.x >= rect_b.x && rect_a.y >= rect_b.y && rect_a.x+rect_a.width <= rect_b.x+rect_b.width && rect_a.y+rect_a.height <= rect_b.y+rect_b.height end
place_rect(node)
click to toggle source
# File lib/bin_packing/bin.rb, line 76 def place_rect(node) num_rectangles_to_process = @free_rectangles.size i = 0 while i < num_rectangles_to_process if split_free_node(@free_rectangles[i], node) @free_rectangles.delete_at(i) num_rectangles_to_process -= 1 else i += 1 end end prune_free_list @boxes << node end
prune_free_list()
click to toggle source
Goes through the free rectangle list and removes any redundant entries.
# File lib/bin_packing/bin.rb, line 158 def prune_free_list i = 0 while i < @free_rectangles.size j = i + 1 while j < @free_rectangles.size if is_contained_in?(@free_rectangles[i], @free_rectangles[j]) @free_rectangles.delete_at(i) i -= 1 break end if is_contained_in?(@free_rectangles[j], @free_rectangles[i]) @free_rectangles.delete_at(j) else j += 1 end end i += 1 end end
split_free_node(free_node, used_node)
click to toggle source
# File lib/bin_packing/bin.rb, line 93 def split_free_node(free_node, used_node) # Test with SAT if the rectangles even intersect. if used_node.x >= free_node.x + free_node.width || used_node.x + used_node.width <= free_node.x || used_node.y >= free_node.y + free_node.height || used_node.y + used_node.height <= free_node.y return false end try_split_free_node_vertically(free_node, used_node) try_split_free_node_horizontally(free_node, used_node) true end
try_leave_free_space_at_bottom(free_node, used_node)
click to toggle source
# File lib/bin_packing/bin.rb, line 124 def try_leave_free_space_at_bottom(free_node, used_node) if used_node.y + used_node.height < free_node.y + free_node.height new_node = free_node.clone new_node.y = used_node.y + used_node.height new_node.height = free_node.y + free_node.height - (used_node.y + used_node.height) @free_rectangles << new_node end end
try_leave_free_space_at_top(free_node, used_node)
click to toggle source
# File lib/bin_packing/bin.rb, line 116 def try_leave_free_space_at_top(free_node, used_node) if used_node.y > free_node.y && used_node.y < free_node.y + free_node.height new_node = free_node.clone new_node.height = used_node.y - new_node.y @free_rectangles << new_node end end
try_leave_free_space_on_left(free_node, used_node)
click to toggle source
# File lib/bin_packing/bin.rb, line 140 def try_leave_free_space_on_left(free_node, used_node) if used_node.x > free_node.x && used_node.x < free_node.x + free_node.width new_node = free_node.clone new_node.width = used_node.x - new_node.x @free_rectangles << new_node end end
try_leave_free_space_on_right(free_node, used_node)
click to toggle source
# File lib/bin_packing/bin.rb, line 148 def try_leave_free_space_on_right(free_node, used_node) if used_node.x + used_node.width < free_node.x + free_node.width new_node = free_node.clone new_node.x = used_node.x + used_node.width new_node.width = free_node.x + free_node.width - (used_node.x + used_node.width) @free_rectangles << new_node end end
try_split_free_node_horizontally(free_node, used_node)
click to toggle source
# File lib/bin_packing/bin.rb, line 133 def try_split_free_node_horizontally(free_node, used_node) if used_node.y < free_node.y + free_node.height && used_node.y + used_node.height > free_node.y try_leave_free_space_on_left(free_node, used_node) try_leave_free_space_on_right(free_node, used_node) end end
try_split_free_node_vertically(free_node, used_node)
click to toggle source
# File lib/bin_packing/bin.rb, line 109 def try_split_free_node_vertically(free_node, used_node) if used_node.x < free_node.x + free_node.width && used_node.x + used_node.width > free_node.x try_leave_free_space_at_top(free_node, used_node) try_leave_free_space_at_bottom(free_node, used_node) end end