buhii · October 3, 2015 19:30 · Oct 3, 2015
diff --git a/packer.py b/packer.py
@@ -0,0 +1,216 @@
+# -*- 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()