algorithm - 在多边形内移动多边形

Question

我在找出解决以下问题的算法时遇到了麻烦：

我希望用户能够将矩形（可以是任何类型的多边形）捕捉到多边形的 4 个角，使其尽可能远离多边形内部。

到目前为止我正在尝试什么：

1. 允许用户获取对象。
2. 找到多边形上距离矩形最近的顶点。
3. 找到矩形上最远的顶点到多边形最近的顶点。
4. 使用平面找到与最远矩形点到多边形点的第一个交点。
5. 根据最远点是否在 x/y 坐标中更远，使用相应的 x/y 平面向上或向下移动。
6. 继续重复上述步骤，直到一切都在里面。

标签： algorithm

Answer 1

只要封闭多边形是凸的，您就可以将其写为线性规划问题，然后应用https://en.wikipedia.org/wiki/Simplex_algorithm来找到答案。您放入的较小多边形可以根据需要复杂。

您的不等式是确保较小多边形的每个顶点都在较大多边形内部的所有条件。您不必在这里很聪明，不会出现额外的不平等是没有成本的。

要优化的函数构造如下。查看您尝试接近的顶点的内角。在该点绘制一个坐标系，一个轴直接指向多边形（称为该轴y），另一个与第一个成直角（称为该轴x）。您想最小化您要y放入的多边形上最近顶点的值。（只需将要放入的多边形放在中间，然后搜索最近的顶点。使用它。

您找到的解决方案是将两个顶点尽可能靠近的解决方案，条件是较小的多边形必须位于较大的多边形之内。