# Fill an Area with 4 differnet size rectangles (in a random order) [1000 points]

I have 3 squares and 1 rectangle with these sizes:

200 x 200
300 x 300
400 x 400

and 1 rectangle

200 x 400

What I need to do is given a larger rectangle which will always change, fill it with random amounts of the above four shapes in random orders. I would need to be able to change the shapes from time to time as well (they will always be square or rectangles though).

Does anyone have any idea how I can do this?  I am not looking for code, just some pointers.

LVL 1
###### Who is Participating?

Commented:
An idea (a simple to implement, but, unefficient way):
Because the sizes are pre-defined and constant, you can work on a discete grid (like a matrix).
You can actually say that the sizes are 2,3 & 4, and then multiply them by 100 after solving the problem.
So:
Lets say that the area (A) is of size NxM (after deviding it by 100).
-Create an area of size (N+4)x(M+4) at least (call it F).
-Take a random shape, try to fit the shapes into F (by tring to put each shape to the first available point it fits, scanning row by row). If it fit's nowhere, try the next shape (until trying all of them)
-When getting stuck (can't fit anymore shapes), check if there is an area in F of size NxM which is totally filled up, if yes then take it as A, if no repeat the process from the beginning.

If you will take larger F area the avarege number of repeatitions will be smaller, but each repeatition will take longer.

Good Luck.
0

Commented:
-------  ----  ----  ----
|  A   | | B | | C | | D |
|------| |---| |---| |---|

Now above are the figures you gave A(rectangle) B,C,D(squares) right? suppose you have a larger rectangle F.
Here are some of the questions:
1. F will always change it's size and position?
2. A,B,C,D has to perfectly fit in F? or partially will do?
3. Do you need to fill F completely? or some open space will do?
4. overlap of A,B,C,D is ok? or there shouldn't be any overlap?

Final question, do you need logic for filling F? or you need logic for creating F also?

I may be able to think if you answer these questions.. thanks.

Jamanat
0

Author Commented:
hi jamanat,

1 - F will be different, I will let the user decide the actual size, but I am going to say it will always be a rectange.

2 - They don't have to fit perfectly, they can go outside of F, but by the smallest amount possible

3 - I need to fill it completly

4 - there can't be any overlap - but if it is not possible that the shapes fit together (as one is 300 (as opposed to 200 or 400) and so they won't be even) then it is possible to cut the shapes but I would like to avoid this as much as possible.

I just need the logic for filling f.

thanks, I am really not sure how to do this so any help you can give would be great.
0

Author Commented:
any ideas?
0

Author Commented:
yeah, i got a mate to explain it at the weekend and this is basically what he said so I think this is what I will do.

cheers
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.