-1
$\begingroup$

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º). tree

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). enter image description here

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. ...
...
Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
0
$\begingroup$

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)

Improve this answer
$\endgroup$
5
  • $\begingroup$ why do you start at y=x=1? instead of 0? $\endgroup$
    – E. Williams
    Sep 16, 2017 at 7:17
  • $\begingroup$ 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. $\endgroup$
    – sbzk
    Sep 17, 2017 at 8:16
  • $\begingroup$ 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. $\endgroup$
    – sbzk
    Sep 17, 2017 at 8:17
  • $\begingroup$ 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.) $\endgroup$
    – E. Williams
    Sep 17, 2017 at 19:08
  • $\begingroup$ 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. $\endgroup$
    – sbzk
    Sep 18, 2017 at 10:00
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – E. Williams
    Sep 15, 2017 at 6:19
  • $\begingroup$ @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 $\endgroup$
    – Stella Biderman
    Sep 15, 2017 at 11:31
  • $\begingroup$ Thanks have you got a more extensive explanation about this idea? $\endgroup$
    – E. Williams
    Sep 15, 2017 at 12:58
  • $\begingroup$ @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. $\endgroup$
    – Stella Biderman
    Sep 15, 2017 at 13:00

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