subdivide.py

from collections import namedtuple
from string import lowercase

Rect = namedtuple('Rect', ['name', 'weight'])

# finds the sum of a list of rects
def rects_sum(rects):
  return sum(rect.weight for rect in rects)

# finds the difference between the minimum aspect ratio of rectangles in the subdivison and a perfect square
# takes the height of the rectangles in the subdivision and the values of rectangles in subdivision
def cost(y, subdivision):
  subdivision_sum = rects_sum(subdivision)
  # the width of all the rectangles
  width = subdivision_sum / y
  # the heights of all the rectangles
  heights = [y * float(rect.weight) / subdivision_sum for rect in subdivision]
  dimensions = [(width, height) for height in heights]
  aspect_ratios = [max(dimension) / min(dimension) for dimension in dimensions]
  return max(aspect_ratios)

# takes width, height, and a list of weighted values
# sum(values) == x *y
# x is always > than y
# values is sorted in descending order, 5, 4, 3, ...
# returns a list like [6, 6, [4, 3, [2, [2, [1]]]]]
def subdivide(x, y, values):
  # take the first rectangle
  subdivision = values[0:1]
  # the distance of the minimum aspect from being a square
  current_cost = cost(y, subdivision)

  while len(subdivision) < len(values):
    # pop the next rectangle on
    next_subdivision = subdivision + [values[len(subdivision)]]
    next_cost = cost(y, next_subdivision)
    # if we didn't improve, we're done
    if next_cost > current_cost:
      break

    subdivision = next_subdivision
    current_cost = next_cost

  # the remaining values
  remaining = values[len(subdivision):]

  if len(remaining) == 0:
    return subdivision
  else:
    # the remaining x space left
    remaining_x = x - rects_sum(subdivision) / y

    # to keep preconditions, find the maximum and minimum of next
    next_x = max(remaining_x, y)
    next_y = min(remaining_x, y)
    return subdivision + [subdivide(next_x, next_y, remaining)]

# create a bunch of Rects
weights = [6, 6, 4, 3, 2, 2, 1]
rects = map(Rect._make, zip(lowercase, weights))

treemap = subdivide(6, 4, rects)

print treemap