Fitting one Polygon in another

Question

I have two Polygons A and B and I want to find the position, rotation and scale of B, so it fits into A and has the maximum Area possible. Also both can be concave.

I did some research but couldn't find anything fitting. Maybe someone here can help or give me something that could be helpful.

Answer 1

Here are two references. The first, a 1981 paper, provides an algorithm to solve the problem allowing translations and rotations, but not scaling:

Chazelle, Bernard. "The polygon containment problem." Carnegie-Mellon University, Department of Computer Science, 1981.

This was followed in 1994 by an algorithm that includes scaling. The algorithm uses parametric search:

Sharir, Micha, and Sivan Toledo. "Extremal polygon containment problems." Computational Geometry-Theory and Application 4, no. 2 (1994): 99. (Elsevier link.)
         

All algorithms are polynomial in the number of vertices of the two polygons. In the latter paper, the time complexity is $O(k^2 n \lambda_6(kn) \log^3(kn) \log\log(kn))$, where the containing polygon has $n$ vertices and the contained has $k$ vertices. For $k=n$, this is a bit beyond $O(n^5)$. Various speed-ups can be achieved if one or the other polygon is known to be convex, or if one restricts the rigid motions allowed.

Google Scholar shows about 50 papers that subsequently cite Sharir-Toledo. Packing applications have led some researchers to more practical approximation algorithms.

Answer 2

Here are some observations which might help:

• The space of translations, rotations, and scales you need to consider for fixed A and B is compact, and can be parameterized by a bounded subset of $\mathbb{R}^4$, with an upper bound on the radius of this subset computable from the list of vertices of $A$ and $B$.

• The area of $A \cap B$ is uniformly continuous with respect to (and can be computed from) the position, scale, and rotation of B, with some modulus of continuity computable from the list of vertices for $A$ and $B$.

  • The basic technique for doing this is to find triangulations of A and (the rotated/scaled/translated copy of) B. The area of the intersection is just the sum of the areas of the intersections of triangles, so the problem reduces to computing the area of the intersection of two triangles whose vertices you know.

• The distance between $B$ and $A^c$ is uniformly continuous with respect to (and can be computed from) the position, scale, and rotation of B, with some modulus of continuity computable from a list of vertices for $A$ and $B$.

  • Similar idea as a above using triangulations. You can use this to figure out whether, given some rotation/scaling/translation, B is strictly contained entirely in A: this is so if and only if this distance is strictly positive.

What these tell us is that the maximum area is computable from a list of vertices of A and B. To find an approximation to the maximum area, just check an $\epsilon$-net of points in the parameter space. Your approximation is just the maximal area obtained by those of these finitely many possibilities which have distance between $B$ and $A^c$ at least $\epsilon$. You can use the modulii of continuity computed above to figure out how close your approximation to the maximal area is to the actual maximal area. You can prove as $\epsilon \rightarrow 0$ this approximation converges to the correct area, and you can even compute a decent a priori bound on the rate of convergence.

For actually computing the rotation, translation, and scale that yield this maximal area: it is computable if it is unique.