Numba implementation of Guillotine bin packing

binpack2.py

import numba as nb
from numba.typed import List

NO_ID = -1
DOESNT_FIT = 99999999
NO_SECTION = (0, 0, 0, 0, DOESNT_FIT)

@nb.jitclass([
    ('x', nb.int32),
    ('y', nb.int32),
    ('w', nb.int32),
    ('h', nb.int32),
    ('id', nb.int32),
])
class Rectangle(object):
    def __init__(self, tup):
        x, y, w, h, id = tup
        self.x = x
        self.y = y
        self.w = w
        self.h = h
        self.id = id

    def as_tuple(self):
        return (self.x, self.y, self.w, self.h, self.id)

    @property
    def bottom(self):
        return self.y
    
    @property
    def top(self):
        return self.y + self.h

    @property
    def left(self):
        return self.x

    @property
    def right(self):
        return self.x + self.w 
    
    @property
    def area(self):
        return self.w * self.h
    
    def lt(self, other):
        return self.area < other.area

    def contains(self, rect):
        return (rect.y >= self.y and \
                rect.x >= self.x and \
                rect.y+rect.h <= self.y+self.h and \
                rect.x+rect.w  <= self.x+self.w)     
    
    def intersects(self, rect, edges=False):
        # Not even touching
        if (self.bottom > rect.top or \
            self.top < rect.bottom or \
            self.left > rect.right or \
            self.right < rect.left):
            return False
      
        # Discard edge intersects
        if not edges:
            if (self.bottom == rect.top or \
                self.top == rect.bottom or \
                self.left == rect.right or \
                self.right == rect.left):
                return False

        # Discard corner intersects 
        if (self.left == rect.right and self.bottom == rect.top or \
            self.left == rect.right and rect.bottom == self.top or \
            rect.left == self.right and self.bottom == rect.top or \
            rect.left == self.right and rect.bottom == self.top):
            return False
    
        return True

    def intersection(self, rect, edges=False):
        if not self.intersects(rect, edges=edges):
            return None

        bottom = max(self.bottom, rect.bottom)
        left = max(self.left, rect.left)
        top = min(self.top, rect.top)
        right = min(self.right, rect.right)

        return Rectangle((left, bottom, right - left, top - bottom, NO_ID))

    def join(self, other):
        if self.contains(other):
            return True

        if other.contains(self):
            self.x = other.x
            self.y = other.y
            self.w = other.w
            self.h = other.h
            return True

        if not self.intersects(other, edges=True):
            return False

        # Other rectangle is Up/Down from this
        if  self.left == other.left and self.w == other.w:
            y_min = min(self.bottom, other.bottom)
            y_max = max(self.top, other.top)  
            self.y = y_min
            self.h = y_max-y_min
            return True

        # Other rectangle is Right/Left from this
        if  self.bottom == other.bottom and self.h == other.h:
            x_min = min(self.left, other.left)
            x_max = max(self.right, other.right)
            self.x = x_min
            self.w = x_max-x_min
            return True

        return False

@nb.jitclass([
    ('w', nb.int32),
    ('h', nb.int32),
    ('sections', nb.typeof([(0,0,0,0,0)])),
    ('rectangles', nb.typeof([(0,0,0,0,0)]))
])
class Packer(object):
    def __init__(self, w, h):
        self.w = w
        self.h = h
        self.sections = [(0, 0, w, h, NO_ID)]
        self.rectangles = [(0, 0, 0, 0, 0)]
        self.rectangles.pop()

    def add_section(self, tup):
        section = Rectangle(tup)
        section.id = NO_ID
        plen = 0

        while len(self.sections) > 0 and plen != len(self.sections):
            plen = len(self.sections)
            self.sections = [s for s in self.sections if not section.join(Rectangle(s))]

        self.sections.append(section.as_tuple())

    def split_horizontal(self, section_tuple, w, h):
        section = Rectangle(section_tuple)
        if h < section.h:
            self.add_section((section.x, section.y + h, section.w, section.h - h, NO_ID))
        if w < section.w:
            self.add_section((section.x + w, section.y, section.w - w, h, NO_ID))

    def split_vertical(self, section_tuple, w, h):
        section = Rectangle(section_tuple)
        if h < section.h:
            self.add_section((section.x, section.y + h, w, section.h - h, NO_ID))
        if w < section.w:
            self.add_section((section.x + w, section.y, section.w - w, section.h, NO_ID))

    def split(self, section_tuple, w, h):
        section = Rectangle(section_tuple)
        if section.w < section.h:
            return self.split_horizontal(section.as_tuple(), w, h)
        else:
            return self.split_vertical(section.as_tuple(), w, h)

    def section_fitness(self, section_tuple, w, h):
        section = Rectangle(section_tuple)
        if w > section.w or h > section.h:
            return DOESNT_FIT
        return section.area - (w * h)

    def select_fittest_section(self, w, h):
        min_fitness = DOESNT_FIT
        fittest_section = NO_SECTION
        for st in self.sections:
            fitness = self.section_fitness(st, w, h)
            if fitness == DOESNT_FIT:
                continue
            if min_fitness == DOESNT_FIT or fitness < min_fitness:
                fittest_section = st
        return fittest_section

    def add_rect(self, w, h, id):
        section = self.select_fittest_section(w, h)
        if section == NO_SECTION:
            return (-1, -1)
        self.sections = [s for s in self.sections if s != section]
        self.split(section, w, h)
        x, y, _, _, _, = section
        self.rectangles.append((x, y, w, h, id))
        return (x, y)

test_rectpack.py

from contextlib import contextmanager
import time
import json

from binpack2 import Packer
import numpy as np 
from PIL import Image
import pandas as pd 

@contextmanager
def timing(message='operation'):
    then = time.time()
    yield
    elapsed = time.time() - then
    print('{} completed in {:.4f}s'.format(message, elapsed))

if __name__ == '__main__':
    PATH = 'D20170611T205930_IFCB010_roisizes.json'

    with open(PATH) as fin:
        roisizes = json.load(fin)

    roisizes = pd.DataFrame.from_dict(roisizes)
    roisizes['area'] = roisizes['width'] * roisizes['height']
    roisizes = roisizes.sort_values('area', ascending=False)

    print('loaded {} rectangles'.format(len(roisizes['targetNumber'])))

    with timing('compilation'):
        packer = Packer(1000,1000)
        packer.add_rect(10, 10, 1)

    done = set()
    need_more_pages = True

    page = 0

    with timing('run'):
        while need_more_pages:
            need_more_pages = False
            page += 1

            out = np.zeros((2048, 2048), dtype=np.uint8)
            packer = Packer(out.shape[0], out.shape[1])

            for t in roisizes.itertuples():
                if t.targetNumber in done:
                    continue
                w, h = t.width, t.height

                x, y = packer.add_rect(w, h, t.targetNumber)
                if x != -1 and y != -1:
                    done.add(t.targetNumber)
                    color = ((t.targetNumber * 37) % 127) + 127
                    out[x:x+w,y:y+h] = color
                else:
                    need_more_pages = True

            print('did page {}'.format(page))
            Image.fromarray(out).save('page{:02d}.png'.format(page))

I usually try pypy first, if that isn't enough multiprocessing, and rarely rewriting bottleneck modules using C++/Cython

In the meantime here's a cleaner and faster numba implementation.