What kind of non-optimisation packing problem is this?

Question

You start with a big 2D shape (irregular polygon), and a set of smaller shapes. The goal is to figure out if the smaller shapes can fit within the big shape, without any overlaps. Rotations are allowed.

This seems related to packing problems, except I am not trying to optimise an arrangement by shrinking the container or adding more objects: I want to find any arrangement, given objects and a container.

I'm no mathematician, this is a problem arising from a video game I am working on. I want to produce arrangements of shapes (the smaller shapes can be squares, rectangles or circles; the larger shape however is always irregular and actually defined by pixels). My instinct was to just try random locations for each shape until one works; but then I thought: this problem isn't so bespoke, someone else must have thought of this before.

But I cannot find the right name of this geometric problem so as to find research and/or an algorithm that I can start with. I get no farther than packing problems. So can anyone help me here? What should I google?

Answer 1

You can compare the circumscribing diameter of the smaller shape $a$ with the inscribing diameter $b$ of the larger shape. Insertition is possible if $a\le b$. This is a stricter condition than needed, however generalizable to different shapes and independent of rotation. If you want to include rotation then insertition can be possible also for $a>b$ however this is a more difficult task.

You find more information here:

Circumscribed circle

Largest inscribed circle in irregular points

Answer 2

Maybe you could try polygon partition, polygon covering or something like that.

The last link says most of these problems are NP-hard though (and without circles, which I think is harder), so maybe you should try another way around. (ie. build the bigger shape starting from the smallest ones so you make sure it will always fill it).

Here's a link I think it could be useful if you want to split the bigger shapes into polygons https://www.cs.jhu.edu/~misha/Spring16/05.pdf.

Best of luck, the problem seems really interesting.