Skip to content

Instantly share code, notes, and snippets.

@maxov maxov/subdivide.py
Last active Aug 29, 2015

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.