Simple 2D packing for PlotDevice

packer.py

# -*- coding: utf-8 -*-
"""
Simple 2D packing for PlotDevice by Takahiro Kamatani
Based on https://pypi.python.org/pypi/ortoolpy by Saito Tsutomu
License: Python Software Foundation License
"""

class Cut(object):
    V = True
    H = False


class Plane(object):

    def __init__(self, w, h, x=0, y=0):
        assert w > 0 and h > 0
        self.w = w
        self.h = h
        self.x = x
        self.y = y

        self.rgba = (random(), random(), random(), 0.5)

    def __repr__(self):
        return "<Plane %dx%d @%d,%d>" % (self.w, self.h, self.x, self.y)

    def __eq__(self, other):
        return self.w == other.w and self.h == other.h

    def __lt__(self, other):
        "Can I cover whole other plane?"
        return self.w < other.w or self.h < other.h

    def __le__(self, other):
        return self < other or self == other

    def __sub__(self, other):
        if self >= other:
            pass
        else:
            print "something wrong", self, other

        assert self >= other

        return self.w * self.h - other.w * other.h

    def cut(self, depth, cut_dir):
        if cut_dir == Cut.H:
            if depth == self.h:
                return [self]
            elif depth < self.h:
                return [
                    Plane(self.w, depth,
                          self.x, self.y),
                    Plane(self.w, self.h - depth,
                          self.x, self.y + depth)
                ]

        elif cut_dir == Cut.V:
            if depth == self.w:
                return [self]
            elif depth < self.w:
                return [
                    Plane(depth, self.h,
                          self.x, self.y),
                    Plane(self.w - depth, self.h,
                          self.x + depth, self.y)
                ]

        return []

    def guillotine(self, other, first_cut_dir):
        cut_order = [first_cut_dir, (not first_cut_dir)]

        if first_cut_dir == Cut.V:
            depth_order = [other.w, other.h]
        else:
            depth_order = [other.h, other.w]

        planes = self.cut(depth_order[0], cut_order[0])
        planes = planes[0].cut(depth_order[1], cut_order[1]) + [planes[1]]
        return planes

    def max_offset_guillotine(self, other):
        if self < other:
            return []

        if self == other:
            return [self]

        offset_v = (self.w - other.w) * self.h
        offset_w = (self.h - other.h) * self.w

        if offset_w < offset_v:
            return self.guillotine(other, Cut.V)
        else:
            return self.guillotine(other, Cut.H)

    def __mod__(self, other):
        return self.max_offset_guillotine(other)

    def draw(self, filled=True):
        nofill()
        strokewidth(1)
        stroke(0.3, 0.3, 0.3, 0.5)
        rect(self.x, self.y, self.w - 1, self.h - 1)

        if filled:
            nostroke()
            fill(*self.rgba)
            rect(self.x, self.y, self.w, self.h)


class Container(object):

    def __init__(self, w, h, x=0, y=0):
        self.w = w
        self.h = h
        self.x = x
        self.y = y
        self.planes = [Plane(w, h, 0, 0)]
        self.fixed = []

    def __repr__(self):
        return repr(self.planes)

    def __gt__(self, other):
        return any(filter(lambda p: p > other, self.planes))

    def __imod__(self, other):
        assert isinstance(other, Plane)

        most_similar = self.find_most_similar_plane(other)
        if not most_similar:   # could not find most similar plane
            return self

        del self.planes[self.planes.index(most_similar)]
        fragments = most_similar % other
        for p in fragments:
            if p == other:
                self.fixed.append(p)
            else:
                self.planes.append(p)

        return self

    def rate(self):
        fixed_area = sum(map(lambda p: p.w * p.h, self.planes))
        return self.w * self.h / float(fixed_area)

    def find_most_similar_plane(self, other):
        min_diff = 1e100
        result = None

        for p in self.planes:
            if p < other:
                continue
            if (p - other) < min_diff:
                min_diff = p - other
                result = p

        return result

    def draw(self):
        translate(self.x, self.y)

        for p in self.planes:
            p.draw(filled=False)

        for p in self.fixed:
            p.draw()

        translate(-self.x, -self.y)


class Solver(object):

    def __init__(self, container, items):
        self.new_container = lambda: Container(container.w, container.h)
        self.items = items
        self.container = self.new_container()

    def solve(self):
        container = self.new_container()

        for item in shuffled(self.items):
            container %= item

        if self.container.rate() < container.rate():
            self.container = container

    def draw(self):
        self.container.draw()


# --- main ---
size(300, 300)
speed(10)

NUM_ITEMS = 100


def setup(env):
    container = Container(280, 280)
    items = [Plane(random(50, 200), random(50, 200)) for _ in range(NUM_ITEMS)]

    env.solver = Solver(
        container=container,
        items=items
    )


def draw(env):
    translate(10, 10)
    env.solver.solve()
    env.solver.draw()