|
| 14 Mar 2014 12:24 PM |
So I have a box of a set size and a number of squares. I want to tile these squares inside the box to fill the most area possible while still fitting. Left over space is fine since the squares can't be divided and must be the same size.
Any ideas how to accomplish this? I've tried a few things, but haven't really succeeded. I have found one possible solution, but I don't quite understand it. Perhaps it could help someone? math.stackexchange.com/questions/466198/ |
|
|
| Report Abuse |
|
|
Absurdism
|
  |
| Joined: 18 Jul 2013 |
| Total Posts: 2568 |
|
|
| 14 Mar 2014 12:57 PM |
The guy on StackExchange is right. His "beginner's method" is really easy to understand.
Let us say we have a 5x6 box and we want to fill it with 9 squares. The area of the box is 30 (5*6 = 30). Now, if we do this the non-optimal way, we divide 30/9 to get the area of one square. Though this is not optimal, we know that it is indeed the _maximum_ area for the square. If it is any more, then the box will overflow. Take this visual (to scale of 100):
i imgur com/aE8TZvI.png
Basically, he says we must fill one axis. We can't fill both, but we can fill one. The algorithm we'll employ checks the x-axis first. The area of a square is defined by the square of the side length. That is:
A = x^2 30/9 = x^2
Now we rearrange this equation:
sqrt(30/9) = x
We have now found the maximum side length of the square. So, we divide the length on the x-axis by the side length, or 5/(sqrt(30/9)). We then round this number up to get 3. I'll post this to show someone is actually replying, then I'll continue in a follow-up post. |
|
|
| Report Abuse |
|
|
Absurdism
|
  |
| Joined: 18 Jul 2013 |
| Total Posts: 2568 |
|
|
| 14 Mar 2014 01:08 PM |
The 3 we received is now what we're going to call p_x. This means we can try to divide the length 6 into 3 parts (p_x parts). The area of such a square would be (5/3)^2 using that formula up there. If we multiply this by our number of desired squares, we get 25. So we fill 25 of 30 units. If these squares squeeze together horizontally, then we p_x++ until math.ceil(6/(5/p_x)) >= 9, or the desired number of squares.
If we repeat this substep of the algorithm for the y-axis, and save the number of parts as p_y, then we get that 6/(sqrt(30/9))*9 = 29 units of 30. We now take the greater number between x/p_y and y/p_x. This is the optimal side length. |
|
|
| Report Abuse |
|
|
|
| 14 Mar 2014 01:14 PM |
| Thanks, I think you covered the parts that weren't 100% clear on stackexchange. I'm still working it out, but I think I've got what I need. I will return if something goes terribly wrong. :p |
|
|
| Report Abuse |
|
|
Absurdism
|
  |
| Joined: 18 Jul 2013 |
| Total Posts: 2568 |
|
|
| 14 Mar 2014 01:17 PM |
Here is the algorithm in Lua. I've swapped p_x and p_y to make it a bit easier to understand. I'm sure you'll follow the code.
findSLOfSquares = function(x, y, n) local p_x, p_y = math.ceil((n*x/y)^.5), math.ceil((n*y/x)^.5) local sideX, sideY = math.floor(p_x*y / x)*p_x < n and y/math.ceil(p_x*y/x) or x/p_x, math.floor(p_y*x / y)*p_y < n and x/math.ceil(x*p_y/y) or y/p_y
return math.max(sideX, sideY) end
|
|
|
| Report Abuse |
|
|