Find maximum area polygon inscribed in larger polygon

Question

I would like to find the rotation and location for a polygon that maximizes how large it can be scaled up within the constraints of fitting within a larger polygon.

Current idea is to use scipy optimization routines for optimizing position and rotation parameters to maximize the scaling parameter, and shapely to add a constraint that the polygon is contained. This seems like it'll be slow and not particularly elegant.

Other ideas?

Answer 1

This problem sounds like it might be NP-Hard. Given a candidate solution you can't really be certain that it is the best solution. It seems like you'd need to try to use some sort of incremental randomized search.

Answer 2

If the internal polygon is maximally scaled, then there are at least 4 pairs "internal vertice - external edge" or "external vertice - internal edge" where the vertice is on the edge.

Let's take all 4s of vertice-edge pairs. For every one we get the system of linear equations for two reference points' coordinates. If it has one solution, we verify that there are no intersections and if OK we remember the coordinates and size of the internal polygon.

This is an exact solution, but it's slow. On the other hand, scipy optimization routines are likely to find a local maximum which is not the global one.