quick and dirty 2D rectangle packer, for best results insert items in sorted order largest to smallest

repack.py

class Rect:

    def __init__(self, left, top, right, bottom):

        self.left = left
        self.top = top
        self.right = right
        self.bottom = bottom

    def width(self):
        return self.right - self.left

    def height(self):
        return self.bottom - self.top

class Page:

    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.free_rects = [ Rect( 0, 0, width, height ) ]
        self.occupied_rects = []

    def external_clipped_rects( a, b ):
        top, bottom = a.top, a.bottom
        if ( a.top < b.top ):
            top = b.top
            yield Rect( a.left, a.top, a.right, b.top )
        if ( a.bottom > b.bottom ):
            bottom = b.bottom
            yield Rect( a.left, b.bottom, a.right, a.bottom )
        if ( a.left < b.left ):
            yield Rect( a.left, top, b.left, bottom )
        if ( a.right > b.right ):
            yield Rect( b.right, top, a.right, bottom )

    def insert( self, width, height ):
        for free_rect in self.free_rects:
            if free_rect.width() < width or free_rect.height() < height: continue
            rect = Rect( free_rect.left, free_rect.top, free_rect.left + width, free_rect.top + height )
            self.occupied_rects.append( rect )
            self.free_rects.remove( free_rect )
            free_count = len( self.free_rects )
            for clipped_rect in Page.external_clipped_rects( free_rect, rect ):
                self.free_rects.append( clipped_rect )
            if free_count != len( self.free_rects ):
                self.free_rects.sort( key=lambda x: (x.height()) )
            return rect

    def calculate_efficency( self ):
        total_area = self.width * self.height
        used_area = sum( [ rect.width() * rect.height() for rect in self.occupied_rects ] )
        return used_area / total_area

class Packer:

    def __init__(self, width, height):
        self.pages = [ Page( width, height ) ]
        self.page_width = width
        self.page_height = height

    def insert( self, width, height ):
        for page in self.pages:
            rect = page.insert( width, height )
            if rect: return page, rect
        new_page = Page( self.page_width, self.page_height )
        self.pages.append( new_page )
        return new_page, new_page.insert( width, height )