Bin-packing

A library for placing 2D rectangles (box-es) in one or multiple rectangular areas (bins) with reasonable area allocation efficiency. Rectangles may be rotated by 90 degrees.

This is Maximal Rectangles Algorithm implementation in Ruby. Translated from C++ and improved.

Install

gem install bin_packing

or add the following line to Gemfile:

gem'bin_packing'

and run bundle install from your shell.

Documentation

Add boxes to bin in given order:

require'bin_packing'bin=BinPacking::Bin.new(100,50)boxes=[BinPacking::Box.new(50,50),BinPacking::Box.new(10,40),BinPacking::Box.new(50,44)]remaining_boxes=[]boxes.eachdo |box|
remaining_boxes << boxunlessbin.insert(box)endbin.boxes.size=>2bin.boxes[1].x=>50bin.boxes[1].y=>0bin.boxes[1].packed?=>truebin.efficiency# in percent=>58remaining_boxes.size=>1

Add boxes to one or multiple bins in best-fitting order:

bin_1=BinPacking::Bin.new(100,50)bin_2=BinPacking::Bin.new(50,50)boxes=[BinPacking::Box.new(15,10),# Should be added last (smaller)BinPacking::Box.new(50,45),# Fits in bin_2 better than in bin_1BinPacking::Box.new(40,40),BinPacking::Box.new(200,200)# Too large to fit]packer=BinPacking::Packer.new([bin_1,bin_2])packed_boxes=packer.pack(boxes)packed_boxes.size=>3bin_1.boxes.size=>2bin_1.boxes[0].label=>'40x40 at [0,0]'bin_1.boxes[1].label=>'15x10 at [0,40]'bin_2.boxes.size=>1bin_2.boxes[0].label=>'50x45 at [0,0]'boxes.last.packed?=>false

Specify heuristic for box arrangement in bin:

bin=BinPacking::Bin.new(100,50,BinPacking::Heuristics::BestAreaFit.new)bin.insert(BinPacking::Box.new(50,100)))=> true

Following heuristics are available:

• BestAreaFit - least remaining area
• BestLongSideFit - least remaining side length (worst of both dimensions is more important)
• BestShortSideFit - least remaining side length (best of both dimensions is more important) - default
• BottomLeft - most tallest box is taken

Add boxes with specific, previously known location:

bin=BinPacking::Bin.new(100,50)box=BinPacking::Box.new(40,40)box.x=20box.y=10bin.insert_in_known_position(box)

Add custom data to bins and boxes using inheritance:

classRecordattr_accessor:id,:width,:heightendclassBinWithRecord < BinPacking::Binattr_reader:recorddefinitialize(record)super(record.width,record.height)@record=recordendendclassBoxWithColor < BinPacking::Boxattr_reader:colordefinitialize(width,height,color)super(width,height)@color=colorendendrecord=Record.newrecord.id=321record.width=100record.height=200bin=BinWithRecord.new(record)box=BoxWithColor.new(70,80,'silver')bin.insert(box)=>truebin.record.id=>321bin.boxes.first.color=>'silver'

Export results to HTML:

bin_1=BinPacking::Bin.new(1500,1000)bin_2=BinPacking::Bin.new(500,200)bin_1.insert!(BinPacking::Box.new(950,950))bin_1.insert!(BinPacking::Box.new(500,500))bin_1.insert!(BinPacking::Box.new(200,500))bin_1.insert!(BinPacking::Box.new(250,300))html=BinPacking::Export.new(bin_1,bin_2).to_html(zoom: 0.5)File.write('my/path.html',html)