0

这里有一点数学优化。我需要你的帮助，因为离大学太远了……我正在努力寻找一些真正具体的东西。让我们尽可能精确。

  • 令 R 为任意大小和纵横比的边界矩形（如有必要，假设纵横比不会超过 2/1 和 1/2）。

  • 让 C 是一个圆，其中心在 R 内，并且至少有一个点在 R 内。但是有些点可能在 R 之外。

  • 令 r 为任意纵横比，可能与 R 纵横比不同。

有没有一种已知的算法来调整长宽比为 r 的矩形 R' 的大小和位置，它与 R 完全相交，因此 R' n C 是最大的（n 表示相交，不知道如何在此处输入 MathML）。

我倾向于认为多项式时间内可能不存在完美的解决方案，因此好的近似值可以完成这项工作，即使是可以在超时后停止的迭代解决方案。

我希望 R 和 R' 是非旋转的，即它们的边要么平行于单位矢量，要么垂直于它。但是，如果 R 的两侧平行于 R' 的两侧，并且两者都被任意旋转，那么解决方案将非常适合，那么我将在特定情况下进行。

非常感谢，

马修

4

1 回答 1

1

一些可能有用的观察结果：

1）正如亨利在评论中所说，“如果R'尽可能大，你会得到一个最优值，所以它要么具有相同的高度，要么具有相同的宽度R。这只会留下一个参数（一维位置）来优化。”

2）现在你有一个矩形R'，可以沿着 的高度R或宽度滑动R。我相信您会发现，如果您移动R'使其中心尽可能靠近圆的中心，它将覆盖大部分区域。

3）例如，比率r总是宽度/高度，还是也可以是高度/宽度？换句话说，可以R'旋转以更好地适应R? 如果是这样，您将不得不考虑两个答案 if r != 1。要进行比较，您需要计算R'圆的交集面积。这可能是问题中最难的部分。您是给出圆的半径，还是只知道边缘的某些部分相交R？

4）如果R不平行和垂直于轴，您可以应用平移将圆心带到原点(0, 0)，然后旋转以R与轴对齐。然后求解找到 的角坐标，R'然后对 的角坐标进行反向旋转和反向平移以R'找到最终解。

于 2013-11-02T13:26:51.390 回答