查找以较大多边形刻出的最大面积多边形 [英] Find maximum area polygon inscribed in larger polygon

问题描述

我希望找到一个多边形的旋转和位置，以便在拟合一个更大的多边形的约束条件下，最大化它可以扩大的多大。

< img src =https://i.stack.imgur.com/dbWFh.jpgalt =polygons>

目前的想法是使用 scipy优化例程，用于优化位置和旋转参数以最大化缩放参数， shapely 添加一个包含多边形的约束。这看起来会很慢，并不是特别优雅。

其他想法？

解决方案

如果内部多边形的尺寸最大，那么至少有4对内部顶点 - 外部边缘或外部vertice - 内部边缘，其中vertice位于边缘。

让我们取所有4个顶点边缘对。对于每一个我们都得到两个参考点坐标的线性方程组。如果它有一个解决方案，我们验证没有交点，如果确定，我们记得内部多边形的坐标和大小。

这是一个确切的解决方案，但它是慢。另一方面，scipy优化例程很可能会找到一个不是全局的最大值。

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?

解决方案

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.

这篇关于查找以较大多边形刻出的最大面积多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！