找到内接在较大多边形中的最大面积多边形

Question

我想找到一个多边形的旋转和位置,它可以在一个更大的多边形拟合的约束范围内最大化它的大小.

目前的想法是使用scipy优化例程来优化位置和旋转参数以最大化缩放参数,并且形状地添加包含多边形的约束.这似乎很慢而且不是特别优雅.

其他想法？

Answer 1

这个问题听起来可能是 NP-Hard 问题。给定一个候选解决方案，您无法真正确定它是最佳解决方案。看来您需要尝试使用某种增量随机搜索。