7
$\begingroup$

I'm enamored by the games Unproportional and Unproportional2. The only problem is that they have way too few levels. :)

But, I'm a computer programmer, so I could make my own! With blackjack and hookers the ability to upload custom pictures and randomly generate grids!

Most everything is straightforward there, except for the generation of the grids. How do I take a rectangle and partition it in smaller rectangles? And not only that, I want to be sure that my algorithm can produce ANY possible split within my limitations. (I'll need to add some limitations to make the grids playable. My first idea is to limit the minimum size of rectangle sides, but that will come from playtesting)

Searching for an answer to this I found the CS.SE question "Randomly partition an rectangle into N smaller rectangles". This suggests an algorithm:

  1. Take a rectangle
  2. Randomly do one of the following:
    • Split the rectangle into two rectangles with a line parallel to its sides
    • Split the rectangle into this pattern (with randomize sides and possibly mirrored):
  3. Take each one of the new rectangles and go to point 1. (Recursion)

It's something. But I had doubts if it could produce ALL possible splits. So I took a look at the games, and sure enough, the first level I clicked already had a split which cannot be produced with the above algorithm:

Split

This also gave me inspiration to produce this split, which I think is a minimal example of another split that cannot be produced by the above algorithm:

Split

OK, so if that doesn't work, what does? It feels to me that a problem like this (partitioning a rectangle into smaller rectangles) is something that should have been explored mathematically, but I don't know where how and what to look for.

So, my question is - is there any mathematical research which, either as its primary focus or as a side effect, has developed an algorithm for enumerating all possible splits of a rectangle into smaller rectangles?

$\endgroup$
3
  • 2
    $\begingroup$ You may be interested in the squaring the square problem. Instead of creating the arrangement by cutting up a rectangle, it is much easier to think about sweeping a horizontal line from top to bottom over such an arrangement, and about what kind of changes can occur when the sweep crosses the top or bottom edge of a rectangle. $\endgroup$
    – Jaap Scherphuis
    Aug 24, 2021 at 10:09
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/1116/… and OEIS A181594 $\endgroup$
    – Henry
    Aug 24, 2021 at 12:11
  • $\begingroup$ This question has more to do with geometry than topology, so I've edited the tags accordingly. $\endgroup$
    – Michael Seifert
    Aug 24, 2021 at 16:46

1 Answer 1

Reset to default
7
$\begingroup$

There is an algorithm: with any partition into rectangles, starting at the top-left corner of the big rectangle, take all or part of the top edge or left edge and push it into the big rectangle to give a new partition with an additional small rectangle, constrained by the existing small rectangles.

Here is how to construct what you called your minimal example using this algorithm.

enter image description here

This works because if you consider any possible partition into rectangles, you can always remove the top-left small rectangle by doing this step backwards. Since you start with a finite number of small rectangles and you keep removing one, you must end up with the original big rectangle.

$\endgroup$
7
  • $\begingroup$ Whoa! Good one! Now I need to figure out how to make sure every possible arrangement is equally possible (or thereabouts), and to make sure it produces playable grids... but those are separate questions. Have a checkmark! :) $\endgroup$
    – Vilx-
    Aug 24, 2021 at 11:23
  • $\begingroup$ What if the top left triangle is adjacent to two or more rectangles along both its internal edges? For example your final arrangement but rotated 90 anticlockwise. $\endgroup$
    – Jaap Scherphuis
    Aug 25, 2021 at 15:40
  • $\begingroup$ @JaapScherphuis In that pattern the top-right rectangle (unrotated) is adjacent to two rectangles on its bottom edge, but $1.5$ rectangles on its left edge. Only integers work for this algorithm so the choice would be forced, and at least one edge must have integer rectangles to avoid overlapping rectangles. It is possible to have both as integers involving a $+$ intersection inside the big rectangle, in which case there may be more than one way to construct the partition - imagine a big square made up of four small squares. $\endgroup$
    – Henry
    Aug 25, 2021 at 17:55
  • $\begingroup$ I don't really follow what you mean. But basically I question the assertion "This works because if you consider any possible partition into rectangles, you can always remove the top-left small rectangle by doing this step backwards." $\endgroup$
    – Jaap Scherphuis
    Aug 25, 2021 at 18:09
  • 1
    $\begingroup$ @JaapScherphuis - I am saying that the small rectangle in the the top-left (there must be one) must be attached on its right to the full left sides of other small rectangles or be attached on its bottom side to the full top sides of other small rectangles. So it can be eliminated, with a leftward extension of the other small rectangles in the former case and with an upward extension of the other small rectangles in the latter case. In the process of construction this is reversed, and it is introduced squeezing small rectangles rightwards in the former case, downwards in the latter case $\endgroup$
    – Henry
    Aug 26, 2021 at 1:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .