How many rectangles fit in a large rectangle

[thecow95]

I've tried searching the forums and google, but most answers seem too handle more variables than I have. I need the simplest way to find out how many times a small rectangle can fit in a larger rectangle. All of the packing algorithms I found are made for packing rectangles with varying size. I was hoping it would be a lot simpler when the smaller rectangles are always the same dimension.

I.E. How many 2x5 boxes can you fit in a 13x20 box.

It has been a long time since I had any classes or coded any math algorithms. Any help is appreciated.

[System_Error]

Area of larger rectangle divided by area of smaller rectangle. Is that what you're looking for?

[dsheller]

Simply dividing the areas will not work in all cases. If the rectangle is assumed to be a solid object, you can't cut it, then you would have to figure out how many rectangles can fit horizontally and then find how many can fit vertically. Once you have that you can just multiply those two values and you're done.

For example, in your case: 2x5 boxes in a 13x20. Assuming the units are the same...

You have 13 units to work with in the x direction and a smaller rectangle is 2 units, which means 6 boxes will fit in the x direction. For the y direction you have 20 units to work with and the smaller box is 5 units in the y, therefore you can stack 4 vertically. Now you can simply multiply that together and you get 24 2x5 boxes fit in 1 13x20

And if i'm wrong I blame it on sickness, but that should work even if i got the dimensions screwed up... as I would have screwed it up both times.

[Logophobic]

You can fill the 13x20 with 26 2x5 rectangles.

[thecow95]

Not quite, because if the small boxes were 2x5 and the large one was 1x100, you couldn't fit any. Also, you may hit a situation where the boxes fit like the attached pic.



edit - sorry, my not quite comment was to the very first reply.

[thecow95]

I was thinking maybe I needed to take two paths then compare the results, sort of like

If X > x and Y > y then
--use the method dsheller pointed out
--then see if the remainder of either direction can be turned for more pieces

Then follow the same path again if Y > x and X > y, and the compare the results of the 2 methods and use the larger result.

Not sure if that covers all instances or not, but that is where I am right now.

[thecow95]

Ok, so here is a little suedo-code for what I was trying to describe in the previous post. Any ideas if this is the right track or not?

Big rect dims = X, Y
Small rect dims = x, y

Declare RemX, RemY, TempX, TempY
Declare Total1, Total2, FinalTotal

RemX = -1
If X > x AND Y > y
	Total1 = (X / x) * (Y / y)
	If (X mod x) > y 
		RemY = (X mod x)
		RemX = Y
	Else If (Y mod y) > x
		RemY = X
		RemX = (Y mod y)
		
	If RemX <> -1
		Total1 += (RemX / x) * (RemY / y)

RemX = -1
If Y > x AND X > y
	TempX = Y
	TempY = X
	X = TempX
	Y = TempY
	
	Total2 = (X / x) * (Y / y)
	If (X mod x) > y 
		RemY = (X mod x)
		RemX = Y
	Else If (Y mod y) > x
		RemY = X
		RemX = (Y mod y)
		
	If RemX <> -1
		Total1 += (RemX / x) * (RemY / y)


FinalTotal = MAX(Total1, Total2)