Algorithm to fit shapes to 2D grid?

Question

Let's say you have an n-by-m grid. Some squares are occupied, some are not.

You want to know where in the grid you can fit arbitrary shapes such as to not hit an occupied square. The shapes would variable, and could be x-by-y rectangles, trapezoidal-ish shapes, etc.

Are there algorithmic approaches to this?

Answer 1

This is a form of the Packing Problem.

Here are your options:

• Brute force it as Gajet has mentioned. This can be aided by doing a pre-evaluation of existing space in your world grid, so as to find maximal axis-aligned bounding boxes. This article should give you some insight into how one developer applied solutions to the Packing Problem, in regards to packing arbitrarily-sized sprites into a spritesheet.
• Use a more physically-based approach to the Packing Problem; I call this "Place-and-Grow" for lack of having seen a better term elsewhere. Select a single pixel/cell of your bitmap/source grid to place -- I would start with the centremost pixel. Randomly pick a position in your bacgkround bitmap / destination grid, to place it on. Keep randomising till you find an open space (this process can be optimised in other ways). If it is now overlapping a solid pixel eg. on the left side, push it out in the opposite direction instead (same applies vice versa and for top/bottom). If you now find it in an empty space once more, you're good to go to the next step. "Grow" the pixel in in all 8 directions around itself, in terms of the source grid / bitmap. Then go back and repeat the shifting step to ensure it's not overlapping anything. Rinse, repeat. Eventually you will get to a point where either your image is completely drawn in to background space, or you cannot expand it anymore in any direction, and will have to try again. Basically this approach is described as "physical" because you are pushing away from any boundaries you meet -- until such time as the algorithm is done or it falls out because there is no space on any side to push out toward.

The second "continuous" approach is more organic, and it may in some ways be easier to handle than the large amounts of logic you might have to write for "discrete" Packing Problem solutions (as in the article above). BUT remember that for each subsequent AABB that you "grow" this way to it's maximal size, you will be doing a haphazard, randomised placement -- which may eventually end up being much slower than brute-forcing, as your grid fills up. It will depend on the sparseness of your grid, i.e. the average proportion of filled vs empty cells. If I wanted to do this efficiently, as you seem to, I think I would opt for the first approach. For procedural world generation algorithms, I would find the second approach to be more useful as it would produce more random / less ordered results.

Answer 2

You can optimize Brute force search:

For each point in plane compute how big disk (for example, can be arbitrary bounds) can be placed without colision.

set of (x, y, area of biggest shape to fit at the position)

Sort this by third parameter ("area of biggest shape to fit at the position").

sorted set of (x, y, area of biggest shape to fit at the position) by third value

Compute bounds of Your shape (one You want to place into grid) which are consistent with the sorted set. If You are lucky Your shape would be small enought to be enclosed by one in the sorted set. Finding which one it is is O(log N) for binary search.

Also note, that if You know what sort of shapes are going to be there You can precompute more.