TwoDimPackingClass.py

# 長方形詰め込み
class TwoDimPackingClass:
    """
    2次元パッキング問題
        ギロチンカットで元板からアイテムを切り出す(近似解法)
    入力
        width, height: 元板の大きさ
        items: アイテムの(横,縦)のリスト
    出力
        容積率と入ったアイテムの(id,横,縦,x,y)のリスト
    """
    def __init__(self, width, height, items=None):
        self.width = width
        self.height = height
        self.items = items
    @staticmethod
    def calc(pp, w, h):
        plw, plh, ofw, ofh = pp
        if w > plw or h > plh: return None
        if w*(plh-h) <= h*(plw-w):
            return w*(plh-h), (w, plh-h, ofw, ofh+h), (plw-w, plh, ofw+w, ofh)
        else:
            return h*(plw-w), (plw-w, h, ofw+w, ofh), (plw, plh-h, ofw, ofh+h)
    def solve(self, iters=100, seed_=1):
        from random import shuffle, seed
        bst, self.pos = 0, []
        seed(seed_)
        for cnt in range(iters):
            tmp, szs = [], [(k,w,h) for k,(w,h) in enumerate(self.items)]
            plates = [(self.width, self.height, 0, 0)]
            shuffle(szs)
            while len(szs) > 0 and len(plates) > 0:
                mni, mnr, (k,w,h), szs = -1, [1e9], szs[0], szs[1:]
                for i in range(len(plates)):
                    res = TwoDimPackingClass.calc(plates[i], w, h)
                    if res and res[0] < mnr[0]:
                        mni, mnr = i, res
                if mni >= 0:
                    tmp.append((k,w,h) + plates[mni][2:])
                    plates[mni:mni+1] = [p for p in mnr[1:3] if p[0]*p[1] > 0]
            sm = sum(r[1]*r[2] for r in tmp)
            if sm > bst:
                bst, self.result = sm, tmp
        self.rate = bst / self.width / self.height
        return self.rate, self.result