How to continue this algorithm? [closed]

I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º). I have thought about doing it with a k-ary tree. So each node is a possible placement of a small rectangle. There are 4 combinations to add a rectangle (vertical/horizontal and how does it divide the regions). Where the root node is the empty big rectangle and its children are the first level of possible combinations when adding one rectangle, the second level defines the possible combinations when a second rectangle is added, so on...

I have defined some objects:

BigRectangle:
integer v1, v2, v3, v4 //the 4 vertices that define a BigRectangle.
List<Region> regions //contains a list of Regions contained in BigRectangle.

Region:
integer v1, v2, v3, v4 //the 4 vertices that define a region.
list<SmallRectangle> smallRectangles //contains a list of SmallRectangle contained in Region.

SmallRectangle:
integer v1, v2, v3, v4 //the 4 vertices that define a SmallRectangle.
integer orientation //(0|1) 0-vertical, 1-horizontal.

I am trying to write the algorithm but it is being a mess. I cannot figure out how to write an algorithm to simulate this tree :(

(I am not interested on achieving the best performance)

1. Create and insert an empty BigRectangle as the root.

2. ...
...
• Sep 14 '17 at 21:06
• The decision version of this problem is known as the pallet packing problem and is not even known to be in NP. See cs.smith.edu/~jorourke/TOPP/P55.html#Problem.55 Sep 15 '17 at 6:34
• But I do not find there any real implementation for a solution Sep 15 '17 at 8:00

Since you are not interested in the best performance rather easy coding, it would be a good idea to colour the region of covered area. The algorithm would look like the following:

Colour(x,y,w,d): Fill the rectangle starting from (x,y) to (x+w,y+d).

UnColour(x,y,w,d): Empty the rectangle starting from (x,y) to (x+w,y+d).

Check(x,y,w,d): Verify if rectangle starting from (x,y) to (x+w,y+d) is empty?

maxC = maximum count

PSEUDO-CODE: Invoke SOLVE(w,d,W,D,0)

Solve(w,d,W,D,C)

if(C>maxC) maxC=C

for (y=1,y<=D,y++)

for (x=1,x<=W,x++)

if(Check(x,y,w,d))

Colour(x,y,w,d)

Solve(w,d,W,D,C+1)

UnColour(x,y,w,d)

if(Check(x,y,d,w))

Colour(x,y,d,w)

Solve(w,d,W,D,C+1)

UnColour(x,y,d,w)

• why do you start at y=x=1? instead of 0? Sep 16 '17 at 7:17
• That is just a convention. Depending upon your needs you can either store it in [1,W]x[1,D] or [0,W-1]x[0,D-1]. Either one can be used. Former is sometimes better for understanding, later one is used for efficient coding. Essentially what the code does is try to put a block where ever possible and recurse.
– sbzk
Sep 17 '17 at 8:16
• It can be greatly improved by some techniques/heuristics as follows. (1) If Check(x,y,w,d) is successful, do not try Check(x+x',y+y',w,d) for any x',y'>=0. This is because one can prove any solution from later, can also be achieved using the former. (2) Stopping the Check operation as soon as any unsuccessful cell is found. (3) Using advanced data structures for performing Check, Colour, Uncheck in O(nlog n) time instead of O(n^2) where n = max(w,d). One such data structure is called a Segment Tree.
– sbzk
Sep 17 '17 at 8:17
• Thanks, nice explanation. But could you explain me better the first heuristic? ( (1) If Check(x,y,w,d) is successful, do not try Check(x+x',y+y',w,d) for any x',y'>=0.) Sep 17 '17 at 19:08
• Assume, we have filled the space only from [1,x]x[1,y]. Hence Check(x,y,w,d) is successful and also each Check(x+x',y+y',w,d) for any x',y'>0 are successful. But we essentially would like to pack the rectangles as close as possible. So there is no point leaving a entire row (for x) or column (for y) and placing the rectangle after a gap. What ever solution works for such a placement, will also work for placement at (x,y) as you would only be leaving more space for placement to the right and bottom.
– sbzk
Sep 18 '17 at 10:00

A conceptually far simpler algorithm is to try all the options. Cut the rectangle into $g=gcd(w,\ell)$ squares. There are finitely many ways to portion these squares into non-overlapping blocks that form allowable rectangles. Ennumate them and try all the options.

This is pretty bad, but unless you're going to do something more clever than "try all the options on the tree" it's going to be the same worst case run-time up to factors ignored by big-O. And possibly even the same in all case, I'm not quite sure.

• I cannot understand you, could you please extend your explanation? I would appreciate it. For example for a 4x3 rectangle should you cut it into 1 squares? Sep 15 '17 at 6:19
• @E.Williams Correct. You're cutting it into a grid such that both side lengths of the smaller rectangle are multiples of the grid side length Sep 15 '17 at 11:31
• Thanks have you got a more extensive explanation about this idea? Sep 15 '17 at 12:58
• @E.Williams I'm not sure where my explanation is going awry. So you have a grid and you overlay it on the object square, right? The possible ways to divide the grid squares into rectangles is easier to enumerate than your tree. So you can just enumerate all coverings that way. Sep 15 '17 at 13:00