Dividing up a square into n-quadrilaterals

[sethmachine]

Hi,

This may seem like an odd question but I've got an application for it.

My instances would be Jass rects (making sub-rects out of a giant rect).

I need to take a square (or otherwise regular quadrilateral) and divide it up into n-sub quadrilaterals whose total area encompasses exactly that square.

Parameters:

1) The big square and its dimensions
2) n, the number of sub-sections to make
Optional parameters
3) the minimum size of each subsection (so for example it doesn't do something like 2 giant rectangles and one super tiny small one)
4) maximum size of each subsection (so we don't get super giant quadrilaterals with very many tiny ones).


returns a set of quadrilaterals whose coordinates/area exactly encompasses the original square.

Picture below for n = 8. Obviously there are many possible divisions (I don't think there's an infinite amount for each n though, but I keep changing my mind...), and the algorithm should be non-determinsitic/random, but having some of the optional parameters should help stop wacky things.

Also, what would be the equation to get the total possible combinations of divisions for each n (or is it iinfinite for n > 1?).

e.g.

n = 1 --> (1) there is a single possible division (namely making a square the same size as the original rect)
n = 2 --> (???) I can imagine many ways to do this (but how many exactly?!)

 

[Cokemonkey11]

Mathematically there are an infinite subset of rects for each n>1, but of course using floating point maths there is a (very large) limit.

Also, I'm not sure that an algorithm would be able to uniformly distribute the random rects without vastly longer code. What exactly is this for?

If you can think of any other limits, for example minimum rect size, that might help you design the system.

 

[sethmachine]

Edit2: I've tried googling this stuff and I didn't find anything too helpful (funny I actually found this post…).

But, I think this problem is very much related to an addition problem.

Given some integer, find all subsets of integers whose sum adds exactly to that integer.

set n = 2, and let our integer be 5, here are the solutions: (0, 5), (1, 4), (2,3)

This problem is similar, because the area of the original shape has to be equal to the sum of the areas of each sub-shape. Using the min/max sizes just limits the number of solutions.

If we did min = 2, then for n = 5 there's one solution, namely (2,3). But if we did something wacky, like min = 1 and max = 3, then there is no solution. This is not too hard to calculate.

So I think to solve my problem, we need a solution to this problem...


Well here are some "constants" that should help trim down the problem.

1) The big rect/square will always be the same dimensions (haven't determined these yet).

2) There will always be a minimum subrect size (minSize)

3) There will always be a maximum subrect size (maxSize)

But I don't see how these would be any different from the generalized algorithm, since it'd still just be a call like this

call rectAlgorithm(bigRectSize, numberOfSubRects, minSize, maxSize)

Well the purpose behind this is dynamically generating disjoint sub-regions inside a larger region (where all of these regions total the area/encompoass completely the large region). With that you can do a lot of cool things, that I think would be helpful for generating well-formed dynamic (random) content.

Now I am thinking of a very brute-force solution, an iterative approach, basically how I drew that picture. You randomly make one quadrilateral within the bounds of the square (preferably touching its edges) and then you re-calculate everything, and start over, until the square is encompassed by all the subregions.

Of course you need to keep in mind constraints (e.g. number of subrects), and make sure you keep these satisfied. But they will help constrain what you generate as the algorithm progresses and make future choices "easier" (e.g. placing the nth subrect is super easy, because you have no choice to make about its dimensions, assuming all your steps worked correctly).

I am also thinking of a recursive algorithm, since every time you get a quadrilateral added, you get unused subareas which are also quadrilaterals (though not squares, but since we're using the 4 fields of rects top, bottom, left, right I think any quadrilateral would work as the bigRect).

Am I getting in the right direction?

Edit: Also if you have both a min and max constraint it might possible make the total combinations finite for each n?
maxSize = minSize
e.g. n = 2 (2 (???)) I can imagine two vertical bars across the square, and also two vertical bars down the square, what else is possible?

 

[Cokemonkey11]

I don't know of any algorithm that solves precisely your question, but something has to give.

Remove the variable n and simply define a "minimum size for subsection" then recursively iterate through a region, producing some random integer q subsections to iterate over. This won't ever produce a diagram like the one you've drawn, but again, you never actually said what it is you're solving.

 

[sethmachine]

simplified task

Alright I think I am close to solving this.

I've simplified the task to just this problem:
(note that squares are rectangles too, excuse my mis-use of "quadrilateral.")

Given some rectangle R and n additional rectangles whose total area is exactly the area of R, is it possible to place those rectangles in such a way as to completely cover R?

So if you have n rectangles and sum up all their areas, can they cover up a rectangle whose area is exactly equal to that sum?
e.g.
let Area(r1) = 12 and area(r2) = 13

Can they cover up a rectangle (special case it's a square now) with Area of 25? Yes I think they will.

And while I don't have a proof for the problem I outlined, I think it's true, that is if I sum up the areas of any number of rectangles, I can find a way to glue them together to get a rectangle whose area is exactly that sum (seems trivial with this description).

I came up with a simple algorithm (in Python) that basically computes a valid sequence of the subset sum of some integer (given an integer A, find a set of integers whose sum is exactly A). Not only that, but the algorithm obeys the constraints (minArea, maxArea) of each subrect and how many there must be. Optionally you can relax the constraints and it will modify them (except for n, which is not changeable) to produce a valid sequence. Note if you don't relax the constraints, certain combinations of n, minArea, and maxArea will never yield a possible sequence, and so it will spit back at you saying why.

Subset sum algorithm (python)

def subset_sum(n, value, minV, maxV, malleable = True, total = 0):
    if maxV <= 0 or minV <= 0:
        print "No solution: Either minV or maxV are less than or equal to 0"
        return
    if not malleable:
        if maxV * n < value:
            print "No solution: Given maxV of ", maxV, " but with ", n, " divisions, maxV * n will always be less than ", value
            return
        if minV * n > value:
            print "No solution: Given minxV of ", minV, " but with ", n, " divisions, mixV * n will always be greater than ", value
            return
    if n == 1:
        print value
        print "done"
        return
    else:
        new = random.randint(minV, maxV)
        m = n - 1
        if not malleable:
            while (value - new) < minV * m or (value - new) > maxV * m:
                new = random.randint(minV, maxV)
        total += new
        remainder = value - new
        newMin = minV
        newMax = maxV
        print new, "[", newMin, ",", newMax, "]", " remainder: ", remainder
        if malleable:
            if (newMin * m) > remainder or newMax >= remainder or (newMin * m) < remainder:
                newMin = remainder / m
                newMax = remainder - (m - 1)
        subset_sum(m, remainder, newMin, newMax, malleable, total)

Below is a sample call where I fix
n = 5 (so 5 rects),
Area = 1500 (the area of the big rectangle)
minArea = 250 (each subrect must have an area of at least 250)
maxArea = 400 (each subrect can have at most an area of 400)
malleable = False (the constraints must be obeyed, we can't change min or max during procedure).

Sample call

subset_sum(5, 1500, 250, 400, False)
252 [ 250 , 400 ]  remainder:  1248
394 [ 250 , 400 ]  remainder:  854
326 [ 250 , 400 ]  remainder:  528
273 [ 250 , 400 ]  remainder:  255
255

So with this problem solved, I need to find a way to glue together these rects to cover up the original rectangle, since I should be easily able to convert an area to a JASS rect (the question is where do I put it in the map). The trick is to make sure the rects perfectly cover the big rectangle, so there are no holes. That is the part I work on now.

 

[gorillabull]

So with this problem solved, I need to find a way to glue together these rects to cover up the original rectangle, since I should be easily able to convert an area to a JASS rect (the question is where do I put it in the map). The trick is to make sure the rects perfectly cover the big rectangle, so there are no holes. That is the part I work on now.

first pick some point in the large square as a reference point say u pick the top left corner point then you would have to calculate the length of each side of the rect both initially and after the generation of a new rect. after getting the length of the side you can create a point on the map as the starting point for the next rectangle relative to the reference point (starting point + reference point) inside the large one this can be limited by your min/max side lengths after this you would have created a new square and have to pick another reference point either on the x or y plane

img

although this isnt very efficient and a lot of work to make so u can try making a kd tree instead

 

[sethmachine]

Well I've gotten "close" to some kind of solution.

My algorithm is frankly quite cumbersome--I have fricken 4 nested for loops (so it's a quartic time algorithm, but actually a lot worse than n^4). And I believe my algorithm is actually only covering a single case out of 16 possible cases. The search space is just tremendous it seems in terms of everything that has to be balanced and calculated.

There's no sense in putting the algorithm up, unless someone really wants to help me fix it.

Here is what I've got for this sample run:

n = 6
bigArea = 2550784.00
minArea = 300000
maxArea = 550000
malleable = false

Below are the images--I think it usually breaks when I try to add in the last/sixth rectangle (it overlaps with others). Note that because malleable = false, you usually will get the same sub-rect shapes/positions (always). The sizes do vary occasionally, since there is still some "freedom" in the algorithm.

Sample run with top 3 rects

Sample run with bottom 3 rects

 

[Dr Super Good]

What you do is break up the initial rect into 2 rects and then randomly choose one of those rects and break that into 2 rects, giving you one degree of randomness. How you break it is either horizontally or vertically so this gives you another degree of randomness. Where you make the break is also another degree of randomness. For efficiency you could remove the victim region randomness for a more intelligent constraints given one that breaks up any rect still bigger than the maximum size. And why only into 2, you could break a rect into 3 or 4 for yet another degree of randomness.

After you have n rects you then work on enforcing the constraints. Since these are rects you can alter the non-edge sides positions as much as you want as long as you alter all other rects which share that side iteratively. This needs a side search to get what rects you need to alter and how to change a certain size. These sides are obviously generated by divisions from the previous step so a data structure could be made during division to help here.

All you need to do is keep iterating on various rects, moving non-edge sides until they all fit in the constraints. Some degree of randomness can be added so that rects seldom are on constraint boundaries. A single pass of all rects may not be sufficient for good results but if enough passes are run it should hopefully diverge towards a result that fits the constraints. The best part of this is that it assures 100% area utilisation of the original rect as you reallocate existing allocated space between rects.

How efficient would it be? Very for n rect allocation but probably quite slow for constraint enforcement. For very large n the constraint enforcement stage may need to be staggered over multiple frames to prevent performance issues.

Will you even need constraint enforcement? Maybe the n rect generation step could enforce the constraints at the same time so that it does not sup-divide rects into rects that are too small or leave rects that are too large.

 

[sethmachine]

Would have appreciated your enlightening post a bit more if I had got it before I went into the black hole. If I read correctly, your approach is bottom-up. You just start making divisions and calculations as you go, and hope that you get something good, or just repeat it until you think it approaches the solution.

My approach has been top-down--I immediately decide how many rectangles and their areas and try to glue it together. Arguably this is the harder approach but it would provide an exact result every time and would be done in a single pass, since each iteration is always "correct" with regards to all the constraints.

I came up with a really simple solution though, but it doesn't produce much variability like the example I had shown in the OP.

Take the given rectangle R, calculate its area A and then compute any arbitrary set of positive real numbers subA greater than 0 with cardinality n the sum of whose elements is exactly equal (the subset_sum algorithm I gave above).

Now, all you do is take each area one by one, and convert it into a rectangle whose length is always equal to the length of the giant rectangle. Then you modify the height accordingly (so that its area is equal to what it should be). Then you repeat this for each additional rectangle, making sure to stack it exactly below (or above) the previous. Eventually the sum of the heights will be the height of R, which means you're done.

Obviously this doesn't look too cool. You basically get a bunch of vertical bars. You can go the other direction too (horizontal bars).

The question is now, are there any other solutions possible for a given set of numbers whose sum is the area, restricting their shapes to rectangles (or squares)? Based on my picture in the OP, the answer is yes. But how do we find these not obvious configurations?

For example, if put down our first shape in a random place in R, is there any solution? Well if you say put a square in the middle of R, we then require at least 4 more shapes to fill it up, which means if n < 5 there is no solution.

Square in middle means n >= 5

But we can generalize--if we randomly place the first rectangle and it's not touching any of the edges of R, then we will always need at least 4 other rectangle to cover the remaining area.

If the rectangle ends up touching one of the edges, we will need at least 3 other rectangles.

If the rectangle ends up touching two of the edges, we will need at least 2 other rectangles.

Finally, if the rectangle ends up touching 3 of the edges, we will need at least 1 other rectangle.

(there's a trivial case: if the rectangle touches all the edges, we can't fit any more rectangles (0 other rectangles), because this means it's the same exact shape as R).

So to get variation, we first randomly determine where the first shape goes, and then modify our algorithm based on its position. Obviously if we fail any of the checks, we don't try anything and ask for a higher number of rectangles.

Note also that if we want more variation or finer subRects, each rectangle we add is itself another rectangle which we can apply this division algorithm too. We'd have to tune some parameters to figure out a criteria for which subRect we also split up of course. If we kept applying the algorithm infinitely to every subRect generated, we should basically end up with a bunch of points that fill up the original rectangle.

What is the downside of this approach? Well it doesn't actually find a solution for a given area and its subAreas. Instead it just grows one out, so it's really bottom-up (in line with dr. super good). A top-down approach is I think far too difficult (and not necessary), as I've explored it quite a bit (but that's always the case if you want something done exactly in a single pass).

Here is the high level algorithm which I think would work:

nPartitionAlg takes rectangle R returns nothing
  1.  Decide where our first rectangle goes (0, 1, 2, or 3 sides touching)
  2.  Randomly determine its dimensions and coordinates based on that
  3.  Set remArea = Area(R) - Area(firstRect)
  4.  Create the exact number of rects which fill the empty area
  5.  Loop over all the rects now:
     6.  if rect does not pass our criteria then
       7.  call nPartitionAlg(rect)
  8.  end loop 
  8.  end algorithm

I think this will work. Again will have to fine tune it, but it should make some nice variation once it's done.

 

[Dr Super Good]

Where as my approach...

1. Loop until n rects are made
   2. Find random rect larger than minimum constraint and preferably larger than maximum constraint and divide randomly into 2 (number larger than 2 could be used for big n).
3. Loop for all rects that fail to meet constraints
   4. Resize a movable side of the rects to meet constraints, preferably one where the affected rects have more tolerances to resizing (eg avoid making a rect that is too big even bigger or one that is too small smaller).

This guarantees you 100% area utilization and should mostly produce good results just with a well designed stage 1 and 2.
[/code]

 

[sethmachine]

I never did well in the constraint satisfaction courses--I think I am just not yet capable of understanding your method (I need to get smarter, etc.).

Anyways, I went ahead and implemented the algorithm I outlined.

Here are some of the initial results. The only parameter I've used is the level of recursion, which I pass as a simple integer. So if iter = 0, then the algorithm does a single pass over the seed rectangle and that's it. If iter = 1, it does a pass over the seed rectangle, and then one pass over each of the subrectangles made, and so on (the terminology to state this in math formally is escaping me at the moment).

Hope you enjoy these pictures as much as I did.

Sample rectangles for 2 iterations

iter = 2

iter = 2

iter = 2

iter = 2

iter = 2

iter = 2

Unfortunately, for whatever reason, the algorithm begins to break for anything higher than 2 (and I saw some 2's where a rectangle did get outside the original rectangle). I think it may be an issue with how I set my areas or possibly an overflow I'm not catching. Or I might have a hole in my logic. But there's no errors ever for 0 <= iter < 2, which is odd, because it's recursive. So it shouldn't matter the size of the rectangle (these get smaller obviously for each call). Note you also start to see *singularities*, this is because the lightning effects are not really suitable once you get to these super small rects. I didn't try the algorithm with a much bigger rect yet, but should try that and see if it fixes some problems.

Sample rectangle for 3 iterations

-4

Sample rectangle for 4 iterations

Now I learned I am some how leaking all my rects (or lightning effects or both). If I start off with 5 iterations, and I try to make any more rects in the map, they simply don't appear at all. And the whole map breaks. These images show a -5 call (it never seems to fit completely inside the original rectangle for n > 4). Followed by a -1 call, which requires at most 6 rects. But it only gets a single one.

Sample rectangle for 5 iterations followed by 1 iteration

Edit: I found out the main reason why the algorithm seemed to break. Turns out my logic was correct. What I didn't know was there is a stack limit apparently, and high problem sets invariably caused crashes. I also had a faulty condition for cleaning up the old Quads, but that got fixed. So what remains is trying to avoid this stack limit and also fine tuning the parameters.