bin packing by python

bin_packer.py

#coding=utf8
#siddontang@gmail.com

import random
import math

class Block(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.bin = None


class Bin(object):
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height
        self.used = None
        self.down = None
        self.right = None


def genBlocks(num, minWidth, maxWidth, minHeight, maxHeight):
    assert num > 0
    assert maxWidth > minWidth
    assert maxHeight > minHeight

    blocks = []
    for i in xrange(num):
        width = random.randint(minWidth, maxWidth)
        height = random.randint(minHeight, maxHeight)
        block = Block(width, height)
        blocks.append(block)

    return blocks

def getSortFun(sortType):
    sortTypes = {}
    sortTypes['width'] = lambda block: -block.width
    sortTypes['height'] = lambda block: -block.height
    sortTypes['area'] = lambda block: -block.width * block.height
    sortTypes['maxside'] = lambda block: -max(block.height, block.height)

    return sortTypes[sortType]

def sortBlocks(blocks, sortType):
    sortFunc = getSortFun(sortType)
    blocks.sort(key = sortFunc)
    return blocks

class BinPacking:
    def __init__(self, blocks):
        assert blocks
        block = blocks[0]

        self._root = Bin(0, 0, block.width, block.height)
        self._blocks = blocks

        self._pack()

    def boxSize(self):
        width = self._root.width
        height = self._root.height

        width = math.pow(2, int(math.ceil(math.log(width, 2))))
        height = math.pow(2, int(math.ceil(math.log(height, 2))))
        return (int(width), int(height))


    def _pack(self):
        for block in blocks:
            bin = self._findBin(self._root, block.width, block.height)
            if bin:
                block.bin = self._splitBin(bin, block.width, block.height)
            else:
                block.bin = self._growBin(block.width, block.height)

    def _findBin(self, bin, width, height):
        if bin.used:
            return self._findBin(bin.right, width, height) or self._findBin(bin.down, width, height)                
        elif ((width <= bin.width) and (height <= bin.height)):
            return bin
        else:
            return None

    def _splitBin(self, bin, width, height):
        bin.used = True
        bin.down = Bin(bin.x, bin.y + height, bin.width, bin.height - height)
        bin.right = Bin(bin.x + width, bin.y, bin.width - width, bin.height)
        return bin

    def _growBin(self, width, height):
        canGrowDown = (width <= self._root.width)
        canGrowRight = (height <= self._root.height)

        shouldGrowRight = canGrowRight and (self._root.height >= (self._root.width + width))
        shouldGrowDown = canGrowDown and (self._root.width >= (self._root.height + height))

        if shouldGrowRight:
            return self._growRight(width, height)
        elif shouldGrowDown:
            return self._growDown(width, height)
        elif canGrowRight:
            return self._growRight(width, height)
        elif canGrowDown:
            return self._growDown(width, height)
        else:
            raise Exception('error')

    def _growRight(self, width, height):
        root = Bin(0, 0, self._root.width + width, self._root.height)
        root.used = True
        root.down = self._root
        root.right = Bin(self._root.width, 0, width, self._root.height)

        self._root = root
        bin = self._findBin(self._root, width, height)
        if bin:
            return self._splitBin(bin, width, height)
        else:
            raise Exception('error')

    def _growDown(self, width, height):
        root = Bin(0, 0, self._root.width, self._root.height + height)
        root.used = True
        root.down = Bin(0, self._root.height, self._root.width, height)
        root.right = self._root
        
        self._root = root
        bin = self._findBin(self._root, width, height)
        if bin:
            return self._splitBin(bin, width, height)
        else:
            raise Exception('error')


if __name__ == '__main__':
    blocks = genBlocks(100, 10, 100, 10, 100)
    sortBlocks(blocks, 'maxside')
    binPacking = BinPacking(blocks)

    from Tkinter import *
    
    (width, height) = binPacking.boxSize()
    print width, height  
    master = Tk()  
  
    w = Canvas(master, width = width, height = height, bg = 'red')

    for block in blocks:
        bin = block.bin
        x, y, width, height = bin.x, bin.y, bin.width, bin.height
        w.create_rectangle(x, y, x + width, y + height, fill="blue")  
  
    w.pack()
    mainloop()