6
$\begingroup$

I'm looking for an algorithm that can partition a rectangle into N smaller rectangles, at random. N will be small (on the order of 5-10 in most cases). It need not be uniformly at random, but at the very least, I'd like to avoid algorithms which completely exclude interesting classes of partitions.

One algorithm I've come across a few times (including a question on Math.SE about the number of ways to do n partitions), is to randomly divide the rectangle in two by drawing an horizontal or vertical line across it, then do the same thing recursively to the resulting smaller rectangles until you get what you want.

The trick here is that although you can get a number of different partitions using this scheme:

binary partitionings

There are some ways of dividing a rectangle into smaller rectangles that this method will never produce:

enter image description here

You can easily see that the divide-and-conquer partitioning will never generate the above, because there's no line that could possibly be the first cut, since no single straight line divides the entire square into two smaller rectangles.

So basically I'm looking for an algorithm to randomly divide a rectangle up into N smaller rectangles, where the results meet the following criteria:

  • Partitioned into exactly N smaller rectangles
  • Everything must actually be a rectangle (no L shapes, etc)
  • No empty space left over

The algorithm as a whole should meet the following criteria:

  • There is no valid partitioning that the algorithm is incapable of producing
  • Can be biased towards certain types of configurations, though the less bias the better.
  • Preferably works with integer indices.
  • Does not operate by generating all possible partitions and then picking one at random.

I don't care about asymptotic complexity much, because I'll be working with small numbers.

Improve this question
$\endgroup$
5
  • $\begingroup$ Are we on a discrete grid, or in continuous space? For instance, in your examples the large square is 4x4 cells and each subrectangle is composed of some number of 1x1 cells (but you never cut a cell in the middle). Are you assuming you want a random distribution over partitions like this, or do you allow other kinds of distributions (e.g., a very skinny rectangle that doesn't have an integer height/width)? Also, you say N will be small; will the dimensions of the large rectangle also be fairly small? $\endgroup$
    – D.W. ♦
    Jan 7, 2017 at 18:06
  • $\begingroup$ @D.W. I'm flexible in this regard. The only real restriction is that the algorithm must support a minimum partition size (relative to the size of the whole rectangle), as this is for a game and these regions need to be visible and clickable. For a discrete grid, this is trivial to ensure. Continuous spaces could allow for some neat extras (like a region whose size is not a whole multiple of the minimum), but avoiding vanishingly small regions is more important. Likewise, I'm willing to limit myself to small rects (and scale up afterwards), but supporting large rects would be even better. $\endgroup$
    – philomory
    Jan 7, 2017 at 19:49
  • $\begingroup$ @philomory Well, if the rectangles are going to be displayed on screen, their co-ordinates are going to have to be rounded to integers. So they may as well be integers, right? $\endgroup$
    – David Richerby
    Jan 12, 2017 at 13:16
  • $\begingroup$ Here's a new kind of split that cannot be generated with the above algorithm: i.stack.imgur.com/PnSPh.png And I believe there are many more such cases. I'm not even sure they can all be classified into a finite classifier. $\endgroup$
    – Vilx-
    Aug 24, 2021 at 8:17
  • $\begingroup$ Aaaand MathOverflow delivers! :) math.stackexchange.com/a/4231794/8983 $\endgroup$
    – Vilx-
    Aug 24, 2021 at 11:23

2 Answers 2

Reset to default
1
$\begingroup$

Here's a simple idea that I believe can generate all partitions. There are two types of subdivisions:

  1. Given a rectangle, randomly generate a horizontal or vertical line to partition it into two subrectangles. (The usual "split in two" rule.)
  2. Given a rectangle, randomly generate a rectangle that fits inside it. Consider the 4 corners of this inner contained rectangle: for each of them, flip a coin and draw a line from this corner outwards towards the outer containing rectangle, with the direction of the line (horizontal or vertical) being determined by what the coin says. Regardless of the directions of the 4 lines, the result will always be 5 rectangles. (Some partitions that can be generated by rule 1 can also be generated this way -- in fact, only 2 of the 16 possible configurations of lines will produce partitions that could not be produced by rule 1.)

At any point in time you will have a set of rectangles (initially, just the original one). Randomly choose one to subdivide (or you could, e.g., choose the biggest, etc.), flip a coin to decide which of the two rules to apply to it, and then apply that rule; keep doing this until you have $n$ rectangles.

Disclaimer: I have no idea how to even think about the set of all partitions, let alone whether the above procedure generates them all with equal probability... Probably not.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I haven't had a chance to implement this yet, but I think it's going to suit my needs well. If the probabilities seem too wildly off, I have some ideas for how to balance it out a bit using weighting. $\endgroup$
    – philomory
    Jan 13, 2017 at 20:58
-3
$\begingroup$

(Disclaimer : I have not thought about throughly nor tested this idea ) ... Why not keep track of the largest available area amongst all of the sections, pick the one with the maximum area and draw a random line segment (either vertical or horizontal) within that selected bounding area. This would create two new section and recurse.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ This is exactly the scheme that's rejected in the question because it can't generate the fourth example. $\endgroup$
    – David Richerby
    Jan 12, 2017 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.