Numba implementation of Guillotine bin packing

binpack3.py

import numba as nb
import numpy as np

DOESNT_FIT = -99999999
NO_SECTION = -1

X = 0
Y = 1
W = 2
H = 3
DELETION_FLAG = 4

DELETED = 0
NOT_DELETED = 1

@nb.jit(inline='always')
def intersects(x, y, w, h, xx, yy, ww, hh):
    self_left, self_right = x, x + w
    self_bottom, self_top = y, y + h
    rect_left, rect_right = xx, xx + ww
    rect_bottom, rect_top = yy, yy + hh

    # 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 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

@nb.jit(inline='always')
def contains(x, y, w, h, xx, yy, ww, hh):
    return yy >= y and xx >= x and yy + hh <= y + h and xx + ww <= x + w

@nb.jit(inline='always')
def join(x, y, w, h, xx, yy, ww, hh):

    if contains(x, y, w, h, xx, yy, ww, hh):
        return True, x, y, w, h

    if contains(xx, yy, ww, hh, x, y, w, h):
        return True, xx, yy, ww, hh

    if not intersects(x, y, h, w, xx, yy, ww, hh):
        return False, x, y, w, h

    if x == xx and w == ww:
        y_min = min(y, yy)
        y_max = max(y + h, yy + hh)
        return True, x, y_min, w, y_max - y_min

    if y == yy and h == hh:
        x_min = min(x, xx)
        x_max = max(x + w, xx + ww)
        return True, x_min, y, x_max - x_min, h

    return False, x, y, w, h

@nb.jitclass([
    ('sections', nb.int32[:,:]),
    ('next_section', nb.int32),
    ('n_sections', nb.int32),
    ('w', nb.int32),
    ('h', nb.int32),
])
class Packer(object):
    def __init__(self, w, h, n):
        # n = maximum number of sections
        self.sections = np.empty((n, 5), dtype=np.int32)
        self.w = w
        self.h = h
        self.reset()

    def reset(self):
        self.sections.fill(0)
        self.next_section = 0
        self.n_sections = 0
        self.append_section(0, 0, self.w, self.h)
     
    def append_section(self, x, y, w, h):
        for i in range(self.sections.shape[0]):
            if self.sections[i,DELETION_FLAG] == DELETED:
                self.sections[i,X] = x
                self.sections[i,Y] = y
                self.sections[i,W] = w
                self.sections[i,H] = h
                self.sections[i,DELETION_FLAG] = NOT_DELETED
                self.n_sections += 1
                if i == self.next_section:
                    self.next_section += 1
                return
        # fatal condition: out of space
        
    def delete_section(self, i):
        self.sections[i,DELETION_FLAG] = DELETED
        self.n_sections -= 1

    def is_deleted(self, i):
        return self.sections[i,DELETION_FLAG] == DELETED

    def add_section(self, x, y, w, h):
        deleting = True
        while self.n_sections > 0 and deleting:
            deleting = False
            for i in range(self.next_section + 1):
                if self.is_deleted(i):
                    continue
                xx, yy, ww, hh = self.sections[i,:4]
                joinp, x, y, w, h = join(x, y, w, h, xx, yy, ww, hh)
                if joinp:
                    self.delete_section(i)
                    deleting = True
        self.append_section(x, y, w, h)
        
    def split(self, xx, yy, ww, hh, w, h):
        # short axis split
        # if ww < hh:
        # short leftover axis split
        if ww - w < hh - h:
            # split horizontal
            if h < hh:
                self.add_section(xx, yy + h, ww, hh - h)
            if w < ww:
                self.add_section(xx + w, yy, ww - w, h)
        else:
            # split vertical
            if h < hh:
                self.add_section(xx, yy + h, w, hh - h)
            if w < ww:
                self.add_section(xx + w, yy, ww - w, hh)

    def section_fitness(self, i, w, h):
        ww = self.sections[i,W]
        hh = self.sections[i,H]

        # best area fit
        if w > ww or h > hh:
            return DOESNT_FIT

        return (ww * hh) - (w * h)

    def select_fittest_section(self, w, h):
        min_fitness = DOESNT_FIT
        fittest_section = NO_SECTION
        
        for i in range(self.next_section + 1):
            if self.is_deleted(i):
                continue
            fitness = self.section_fitness(i, w, h)
            if fitness == DOESNT_FIT:
                continue
            if min_fitness == DOESNT_FIT or fitness < min_fitness:
                fittest_section = i

        return fittest_section

    def add_rect(self, w, h):
        section = self.select_fittest_section(w, h)
        if section == NO_SECTION:
            return (-1, -1)
        x, y, ww, hh = self.sections[section,:4]
        self.delete_section(section)
        self.split(x, y, ww, hh, w, h)
        return x, y

@nb.jit
def pack(w, h, ws, hs, xs, ys, pages):
    n = len(ws)
    p = Packer(w, h, max(n,128)) # should be enough overhead
    need_more_pages = True
    page = 1
    while need_more_pages:
        p.reset()
        need_more_pages = False
        for i in range(n):
            if pages[i] > 0: # already placed
                continue
            x, y = p.add_rect(ws[i], hs[i])
            if x == -1 or y == -1:
                need_more_pages = True
                continue
            xs[i], ys[i] = x, y
            pages[i] = page
        page += 1

If you are going to implement a single algorithm not using a rectangle class is faster, if you intend to implement several it will be a chore to maintain.

Absolutely--I'm only doing one algorithm, and I'm using arrays of primitives instead of lists of objects to boost performance and get around some of Numba's limitations in dealing with classes.

Ok, I think any further optimization will result in diminishing returns, you should try to improve the algorithm for your exact problem.

I was able to optimize this further. It's now about 100-150x faster than rectpack for my use case! In my testing rectpack is running at about 1000 rectangles/s.

Great, if you know the rectangles beforehand and you have big bins were a lot of rectangles are placed, you could further optimize by discarding de sections that are too small to fit the smallest rectangle.

I am in this situation and so I could do that. So I could just skip creating a section if it's too small?

That leads me to a question (don't know if it has any easy answer), which is what is the worst case in terms of how many sections would be needed for a given number of rectangles? I'm using a fixed-length array for the sections which could overflow if it's not large enough. I don't recall anything from the paper about space bounds.

Yes just skip the sections too small in area, width, or height.

Each time you place a rectangle at worst two sections are created and one discarded, so it should be O(n)

@joefutrelle , if you can share any documentation on how to your implementation as a function, it would be useful

@bharathraja I think you're asking if this could be implemented as a function rather than using a class; I considered that but I'm getting acceptable performance with the class-based version.

If you're asking about documentation of the algorithm itself, it can be found here