Spatial organisation of a group of blocks on a grid

Question

I have a grid of cells (empty at beginning), and a collection of blocks which are rectangles or squares whose size are a multiple of a cell (for example, a block might be 2 cells by 3 cells). I won't know all the blocks in advance, but will have to place them as they arrive. In case anyone's wondering, this has to do with placing a bunch of smaller bitmaps on a large one, where all the bitmaps's sizes are a multiple of 32.

I've been thinking that I could simply iterate through the grid, looking for a place to fit the block, and if I find a place, put it there. I could also have a quadtree that keeps tracks of which chunks of the grid are occupied, so I don't have to iterate through already allocated cells much.

I've tried googling for examples and solutions, but since English is not my native language, I've had trouble formulating what I want to search for.

So my question is what algorithms and data structures are used for this kinds of problems? Any suggestions, comments and examples would be appreciated.

Thank you.

Answer 1

I found "The Design and Analysis of Spatial Data Structures." by Hanan Samet to be quite a good reference for problems in this kind of area. It's quite pricey, but your local library might have a copy and it is a good read.

Answer 2

You are searching information on what is called "bin packing" (see http://en.wikipedia.org/wiki/Bin_packing_problem), more precisely, the 2D version of the problem, and even more specificaly, "texture packing".

You might want to have a look there: http://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm (several algorithms and data structures referenced)

If you are really motivated, you can also look at the articles on the subject!

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.3502&rep=rep1&type=pdf

http://citeseerx.ist.psu.edu/search?q=texture+packing&submit=Search&sort=rel