我想找到一个多边形的旋转和位置，以在更大的多边形内拟合的约束范围内最大化它可以放大的大小。
当前的想法是使用scipy 优化例程来优化位置和旋转参数以最大化缩放参数，并匀称地添加包含多边形的约束。这似乎会很慢而且不是特别优雅。
其他想法？
问问题
772 次
2 回答
1
这个问题听起来可能是 NP-Hard。给定一个候选解决方案，您无法确定它是否是最佳解决方案。似乎您需要尝试使用某种增量随机搜索。
于 2013-07-02T20:15:14.397 回答
1
如果内部多边形被最大缩放，则至少有 4 对“内部顶点 - 外部边缘”或“外部顶点 - 内部边缘”，其中顶点位于边缘上。
让我们取所有 4 的顶点-边对。对于每一个，我们得到两个参考点坐标的线性方程组。如果它有一个解决方案，我们验证没有交叉点，如果可以，我们记住内部多边形的坐标和大小。
这是一个精确的解决方案，但速度很慢。另一方面，scipy 优化例程可能会找到一个局部最大值，而不是全局最大值。
于 2013-07-03T06:29:57.003 回答