# How to Divide a Square or Rectangle into squares of different sizes?

For an art project I want to compute a division of space into random squares. I have a number of applications where this would be a pleasant visual layout, I'm trying to figure this out for myself, but I think it might be useful to others too.

Given a 2D space of x width and y height. How do I divide it into squares of varying sizes (factors of the largest possible square for a particular area, some areas will have smaller maximum sized squares due to the initial division of space.)

I will add a diagram later today to illustrate better / more specifically what I am attempting to do.

Thank you.

Edit: I'll want to add a limit for the smaller sizes, as these will be used to display content at a fixed resolution.

-
If you're willing to allow 'fault lines' through your project - that is, lines that slice all the way through it - or even allow for many squares of the same size, then this is straightforward and it comes down to aesthetics. If you want a division into differently-sized squares, the problem gets much harder and somewhat less random; this is known as 'squaring the square', and you can find more information about it under that name at Wikipedia... – Steven Stadnicki Jan 21 '12 at 2:27
@StevenStadnicki - Thank you, I'm intending each large sector to sub divide based on a random probability, bottoming out at a lower limit, eg. squares can't get smaller than n. – Slomojo Jan 21 '12 at 4:17
@StevenStadnicki - Looking into Squaring the Square, it looks like I want Mrs Perkins Quilt style, but the initial shape need not be square, so I'll have to do some initial subdividing up front. – Slomojo Jan 21 '12 at 5:34
The question was originally tagged iteratedsystems and divisionofspace, both of them were used only for this question. I think that new tags should be only created when we can assume that those tags would be useful at least for a few other questions. I've retagged it tiling and algorithms - if someone has a better idea, please, add different tags. – Martin Sleziak Jan 25 '12 at 16:58
How about a random quadtree? Here random means you randomly choose whether to divide a node. – lhf May 21 '12 at 12:18

Turns out what I want is Squaring the Square, as suggested by @StevenStadnicki, the best resource for this is http://squaring.net

There's a ton of information there surrounding the history of squared-squares and rectangles, the first perfectly squared square, that is a square divided by smaller squares all of unique sizes, was successfully calculated in 1939.

In a similar manner to log tables, squared-squares, and squared-rectangles have been catalogued too, these are listed in a notation called Bouwkamp codes or Tablecodes (they both essentially contain the same information, Bouwkamp codes provide parentheses and commas to make them slightly more human readable.)

For example, you can describe a 4x4 imperfect squared square, with all the interior squares the same size, e.g. a 100 unit square, filled with 25 unit squares like this:

Table code...: 16 100 100 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25

Bouwkamp code: 16 100 100 (25,25,25,25) (25,25,25,25) (25,25,25,25) (25,25,25,25)


As you can see, simply stripping the punctuation from a Bouwkamp code gives you an equivalent Table Code.

These code enables you to fill a rectangle, of dimensions described by the 2nd and 3rd indicies, with n squares (as described by the 1st index), the remaining indicies each describe a square within this rectangle/square.

This makes them relatively easy to draw by hand, or using a simple algorithm, as long as you record the current lowest Y axis value, and the width of the gap at that vertical level. The Bouwkamp notation helps when drawing manually, using parentheses to denote the set of squares that fit the next available gap width.

Anyway, for my nefarious uses, they make nice photo framing devices...

-
I think you threw us with the word "random". There's nothing random about the squares in the squaring of a square or a rectangle. – Gerry Myerson May 21 '12 at 3:41
@GerryMyerson I agree, but it's a fair enough place to come from when ignorant of the possible solutions, and they certainly are of "random" sizes, to the lay-person. I feel that as someone without classical math training (such as myself.) Topics like this are difficult to discover. – Slomojo May 21 '12 at 3:56