Spatial organisation of a group of blocks on a grid

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开发者_如何学JAVA my question is what algorithms and data structures are used for this kinds of problems?

---

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: https://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