在一个大多边形内找到最大面积的内切多边形。

Question

8

我希望找到一个多边形的旋转和位置，使其在符合嵌套在另一个更大的多边形的限制条件下，能够最大化被缩放的大小。

polygons

当前的想法是使用scipy优化例程来优化位置和旋转参数，以最大化缩放参数，并使用shapely添加一个约束条件，即多边形被包含在内。这似乎会很慢，而且不是特别优雅。

还有其他的想法吗？

- daedalus12

这些是简单的多边形吗？它们的边数有限制吗？ - Codie CodeMonkey

是的，只是简单的多边形。其中一些可能有数百个面。 - daedalus12

我正在尝试解决类似的问题 - 你能告诉我你从scipy中使用了哪些例程吗？ - George R

2个回答

1

如果内部多边形被最大化缩放，则至少存在4对“内部顶点-外部边缘”或“外部顶点-内部边缘”，其中顶点位于边缘上。

我们考虑所有4个顶点-边缘对。对于每一个，我们得到两个参考点坐标的线性方程组。如果它有一个解，我们验证是否没有交点，如果OK，我们记住内部多边形的坐标和大小。

这是一个精确的解法，但速度较慢。另一方面，scipy优化程序可能会找到一个局部最大值，而不是全局最大值。

- Tanriol

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kenneth Wright · Accepted Answer

这个问题听起来可能是NP-hard问题。给定一个候选解，你不能确定它是否是最优解。似乎需要尝试使用某种增量随机搜索方法。