rectpack

class Node(object):
    def __init__(self, width, height, x = 0, y = 0):
        assert width >= 0 and height >= 0 and x >= 0 and y >= 0, 'width={0}; height={1}; x={2}; y={3}'.format(width, height, x, y)
        self.left = self.right = None
        self.wbound = self.width = width
        self.hbound = self.height = height
        self.x = x
        self.y = y

    # Inserts a new rectangle in the subtree rooted at the given node.
    def insert(self, width, height):
        assert width > 0 and height > 0
        # If this node is an internal node, try both leaves for possible space.
        # (The rectangle in an internal node stores used space, the leaves store free space)
        if self.left:
            return self.left.insert(width, height) or self.right.insert(width, height)

        # This node is a leaf, but can we fit the new rectangle here?
        if width > self.width or height > self.height:
            return None # Too bad, no space.

        # The new cell will fit, split the remaining space along the shorter axis,
        # that is probably more optimal.
        w = self.width - width
        h = self.height - height
        if w <= h: # Split the remaining space in horizontal direction.
            self.left  = Node(w         , height, self.x + width, self.y         )
            self.right = Node(self.width, h     , self.x        , self.y + height)
        else: # Split the remaining space in vertical direction.
            self.left  = Node(width, h          , self.x        , self.y + height)
            self.right = Node(w    , self.height, self.x + width, self.y         )

        # Note that as a result of the above, it can happen that self.left or self.right
        # is now a degenerate (zero area) rectangle. No need to do anything about it,
        # like remove the nodes as "unnecessary" since they need to exist as children of
        # this node (this node can't be a leaf anymore).

        # This node is now a non-leaf, so shrink its area - it now denotes
        # *occupied* space instead of free space. Its children spawn the resulting
        # area of free space.
        self.width = width
        self.height = height
        return self

    def __str__(self):
        return 'Node({0}, {1}, {2}, {3})'.format(self.x, self.y, self.width, self.height)

    def bbox(self):
        return (self.x, self.y, self.x + self.width, self.y + self.height)

    def coverage(self, depth=0):
        #print '{0}{1}, {2}'.format('  '*depth, self.wbound, self.hbound)
        return self.left.coverage(depth + 1) + self.right.coverage(depth + 1) if self.left else self.width*self.height

    def density(self):
        return float(self.coverage())/(self.wbound*self.hbound)