rectangles in rectangle problem

Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.

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

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

Thread images: 2

Anonymous

rectangles in rectangle problem 2016-01-12 09:48:40 Post No. 7778243

[Report] Image search: [iqdb] [SauceNao] [Google]

rectangles in rectangle problem 2016-01-12 09:48:40 Post No. 7778243

[Report] Image search: [iqdb] [SauceNao] [Google]

File: Dolan_duck_hd_hq_by_bojanglesthecat-d52ixnl.png (92 KB, 1280x1152)
Image search:
[iqdb]
[SauceNao]
[Google]

92 KB, 1280x1152

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

>>

File: 2fccd31881a93ae06e50bbf71a3a067afa232eed_full.jpg (3 KB, 184x184)
Image search:
[iqdb]
[SauceNao]
[Google]

3 KB, 184x184

>>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.

Thread images: 2

Thread DB ID: 432494

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's