Packing arbitrary polygons within an arbitrary boundary

Question

I was wondering if anybody could point me to the best algorithm/heuristic which will fit my particular polygon packing problem. I am given a single polygon as a boundary (convex or concave may also contain holes) and a single "fill" polygon (may also be convex or concave, does not contain holes) and I need to fill the boundary polygon with a specified number of fill polygons. (I'm working in 2D).

Many of the polygon packing heuristics I've found assume that the boundary and/or filling polygons will be rectangular and also that the filling polygons will be of different sizes. In my case, the filling polygons may be non-rectangular, but all will be exactly the same.

Maybe this is a particular type of packing problem? If somebody has a definition for this type of polygon packing I'll gladly google away, but so far I've not found anything which is similar enough to be of great use.

Thanks.

Ides

No, this doesn't look like some well-known special case of the packing problem. Anything that works with distinct shapes should trivially work with identical shapes too. If you have an algorithm that works well for a rectangular boundary, you can try to adapt it for an arbitrary boundary. Modify it so that you can at a flip opre-fill your boundary with some shapes that cannot be moved or deleted (e.g. there's only one way to place them). Solve for a rectangular boundary, pre-filled with some shapes that just leave your original boundary unfilled. Not all algorithms can be adapted like this. – Deaden

The case with only one kind of filling polygon is definitely a special case of the general situation with different filling polys. I believe most heuristics for solving this kind of cutting/packing problem uses the no-fit polygon, so googling "no-fit irregular packing"' or something like that could be a good start. – Snocat

I think you should as this in the theoretical cs version of SO. – Humber

for the algorithm: this is commonly called "nesting", which means to pack irregular, potentially non-convex, 2D/3D shapes into some piece of "stock" that is then cut. things need not be nested literally, but they could be. – Lusatia

Answer 1

Thanks for the replies, my requirements were such that I was able to further simplify the problem by not having to deal with orientation and I then even further simplified by only really worrying about the bounding box of the fill element. With these two simplifications the problem became much easier and I used a stripe like filling algorithm in conjunction with a spatial hash grid (since there were existing elements I was not allowed to fill over).

With this approach I simply divided the fill area into stripes and created a spatial hash grid to register existing elements within the fill area. I created a second spatial hash grid to register the fill area (since my stripes were not guaranteed to be within the bounding area, this made checking if my fill element was in the fill area a little faster since I could just query the grid and if all grids where my fill element were to be placed, were full, I knew the fill element was inside the fill area). After that, I iterated over each stripe and placed a fill element where the hash grids would allow. This is certainly not an optimal solution, but it ended up being all that was required for my particular situation and pretty fast as well. I found the required information about creating a spatial hash grid from here. I got the idea for filling by stripes from this article.

Ides

Sorry to accept my own answer, but none of the others were really close enough to how I actually solved my problem for me to say they would have worked. Thanks everybody for the help though. – Ides

Answer 2

The question you ask is very hard. To put this in perspective, the (much) simpler case where you're packing the interior of your bounded polygon with non-overlapping disks is already hard, and disks are the simplest possible "packing shape" (with any other shape you have to consider orientation as well as size and center location).

In fact, I think it's an open problem in computational geometry to determine for an arbitrary integer N and arbitrary bounded polygonal region (in the Euclidean plane), what is the "optimal" (in the sense of covering the greatest percentage of the polygon interior) packing of N inscribed non-overlapping disks, where you are free to choose the radius and center location of each disk. I'm sure the "best" answer is known for certain special polygonal shapes (like rectangles, circles, and triangles), but for arbitrary shapes your best "heuristic" is probably:

1. Start your shape counter at N.
2. Add the largest "packing shape" you can fit completely inside the polygonal boundary without overlapping any other packing shapes.
3. Decrement your shape counter.
4. If your shape counter is > 0, go to step 2.

I say "probably" because "largest first" isn't always the best way to pack things into a confined space. You can dig into that particular flavor of craziness by reading about the bin packing problem and knapsack problem.

EDIT: Step 2 by itself is hard. A reasonable strategy would be to pick an arbitrary point on the interior of the polygon as the center and "inflate" the disk until it touches either the boundary or another disk (or both), and then "slide" the disk while continuing to inflate it so that it remains inside the boundary without overlapping any other disks until it is "trapped" - with at least 2 points of contact with the boundary and/or other disks. But it isn't easy to formalize this "sliding process". And even if you get the sliding process right, this strategy doesn't guarantee that you'll find the biggest "inscribable disk" - your "locally maximal" disk could be trapped in a "lobe" of the interior which is connected by a narrow "neck" of free space to a larger "lobe" where a larger disk would fit.

Landgrabber

Answer 3

This type of problem is very complex to solve geometrically.

If you can accept a good solution instead of the 100% optimal solution then you can to solve it with a raster algorithm.

You draw (rasterize) the boundary polygon into one in-memory image and the fill polygon into another in-memory image.

You can then more easily search for a place where the fill polygon will fit in the boundary polygon by overlaying the two images with various (X, Y) offsets for the fill polygon and checking the pixel values.

When you find a place that the fill polygon fits, you clear the pixels in the boundary polygon and repeat until there are no more places where the fill polygon fits.

The keywords to google search for are: rasterization, overlay, algorithm

Dahna

Answer 4

If your fill polygon is the shape of a jigsaw piece, many algorithms will miss the interlocking alignment. (I don't know what to suggest in that case)

One approach to the general problem that works well when the boundary is much larger than the fill pieces is to tile an infinite plane with the pieces in the best way you can, and then look for the optimum alignment of the boundary on this plane.

Stine