Partition a rectangle into near-squares of given areas

Question

I have a set of N positive numbers, and a rectangle of dimensions X and Y that I need to partition into N smaller rectangles such that:

• the surface area of each smaller rectangle is proportional to its corresponding number in the given set
• all space of big rectangle is occupied and there is no leftover space between smaller rectangles
• each small rectangle should be shaped as close to square as feasible
• the execution time should be reasonably small

I need directions on this. Do you know of such an algorithm described on the web? Do you have any ideas (pseudo-code is fine)?

Thanks.

Answer 1

What you describe sounds like a treemap:

Treemaps display hierarchical (tree-structured) data as a set of nested rectangles. Each branch of the tree is given a rectangle, which is then tiled with smaller rectangles representing sub-branches. A leaf node's rectangle has an area proportional to a specified dimension on the data.

That Wikipedia page links to a page by Ben Shneiderman, which gives a nice overview and links to Java implementations:

Then while puzzling about this in the faculty lounge, I had the Aha! experience of splitting the screen into rectangles in alternating horizontal and vertical directions as you traverse down the levels. This recursive algorithm seemed attractive, but it took me a few days to convince myself that it would always work and to write a six line algorithm.

Wikipedia also to "Squarified Treemaps" by Mark Bruls, Kees Huizing and Jarke J. van Wijk (PDF) that presents one possible algorithm:

How can we tesselate a rectangle recursively into rectangles, such that their aspect-ratios (e.g. max(height/width, width/height)) approach 1 as close as possible? The number of all possible tesselations is very large. This problem falls in the category of NP-hard problems. However, for our application we do not need the optimal solution, a good solution that can be computed in short time is required.

You do not mention any recursion in the question, so your situation might be just one level of the treemap; but since the algorithms work on one level at a time, this should be no problem.

Answer 2

I have been working on something similar. I'm prioritizing simplicity over getting as similar aspect ratios as possible. This should (in theory) work. Tested it on paper for some values of N between 1 and 10.

N = total number of rects to create, Q = max(width, height) / min(width, height), R = N / Q

If Q > N/2, split the rect in N parts along its longest side. If Q <= N/2, split the rect in R (rounded int) parts along its shortest side. Then split the subrects in N/R (rounded down int) parts along its shortest side. Subtract the rounded down value from the result of the next subrects division. Repeat for all subrects or until the required number of rects are created.