Build reversed No-Fit-Polygon

Question

I need some robust algorithm to optimally fit one non-convex polygon into another. The destination one can contain holes.

Recently I found scholarly articles on this subject:

One of them describes way to fit list of polygons into another polygon. Building no-fit-polygon here is mentioned as one of the steps.

Another describes robust and concreete way of building no-fit-polygon with good complexity.

The only issue I struggle with is that in this papers different things are considered to be no-fit-polygon. In the first it lies inside the polygon like this, while in the second it is outside like one this picture and has different meaning.

I understand that actual "no-fit-polygon" notion is described in the second article, but how can I get "reversed" no-fit-polygon, like on the first picture? Maybe it is possible to adjust the algorithm from the second paper for this case?

I'd also love the solution to be implementable in code.

Any help appreciated.

Answer 1

Unless I misunderstand your question, you are seeking to pack one irregular polygon into another. This has been extensively studied under the name the polygon containment problem:

Chazelle, Bernard. The polygon containment problem. Carnegie-Mellon University, Department of Computer Science, 1981. Proves that the problem can be solved in polynomial-time, about $O(n^7)$ in the general case, for polygons of $n$ vertices.

The problem is usually addressed in the context of packing several given polygons into a container. Here is one paper that could lead you to that literature (Google Scholar lists ~50 later papers that cite this one):

Milenkovic, Victor J. "Rotational polygon overlap minimization and compaction." Computational Geometry 10, no. 4 (1998): 305-318. PDF download.

---

         
          ^Fig.7.

---