[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vip /vp / vr / w / wg / wsg / wsr / x / y ] [Search | Home]
rectangles in rectangle problem
If images are not shown try to refresh the page. If you like this website, please disable any AdBlock software!

You are currently reading a thread in /sci/ - Science & Math

ANY GENIUS HERE?
we have n x m grid and a x b rectangles
how to determine if we're able to cover whole grid with these rectangles, and if not what is the biggest ammount of rectangles which would fit?

algorithm/code would be very helpful?
thanks

halp me pls
>>
all rectangles are the same size
>>
I believe that this is the criteria for tiling the whole grid, but correct me if I'm wrong.

Each of a and b must divide either n or m (they may divide the same number or different numbers). If they divide the same number, say a | n and b | n, then you must have m = ax + by for some non negative integers x,y.
>>
Engineer here (sorry).
Does this help?http://www.rmig.com/en/technical+info/formulae/calculation+open+area
>>
>>7778243
Do all the rectangles have the same size?
If they do than it's easy. max(floor(m/b)*floor(n/a), floor(m/a)*floor(n/b)) is the maximum number of rectangles can fit in the m x n grid.
Then you can just fit all of those rects into the grid, if there is any empty space left, then it's impossible to cover the grid with those a x b rectangles.

If the rectangles are not equal in size, then I have a bad news for you.
https://en.wikipedia.org/wiki/Cutting_stock_problem
To get the optimal solution, you have to run the algorithm for quite a long time.