Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement