math - 检测一个矩形是否可以放入另一个矩形

Question

这个问题不同于测试一个矩形是否在另一个矩形中。

已知信息是两个矩形的边长。

如何计算一个矩形是否可以放入另一个矩形？

Answer 1

这是一个很好的问题！当且仅当满足这些条件之一时，具有边和( ) 的较小矩形完全适合具有边p和q( ) 的较大矩形：p >= qaba >= b

或者

请参阅此内容以供参考。

---

因此，如果我们有变量a, b, p, q，我们可以通过评估来检查这种矩形排列是否可行：

(p <= a && q <= b) || (p > a &&
                        b >= (2*p*q*a + (p*p-q*q)*sqrt(p*p+q*q-a*a)) / (p*p+q*q))

---

编辑：感谢@amulware 在他的评论中发布这个替代版本：

Answer 2

第一个检查当然是矩形是否在任何一个轴对齐的方向上都适合另一个。

如果不是，它唯一适合的选择是对角线，但实际上可能有很多角度适合它，困难在于，不仅仅是猜测，而且确实计算一个可能的角度，如果存在的话。

现在，请注意，如果内部矩形确实适合对角线，那么如果它的对角同时接触外部矩形的顶部和底部边缘，或者左侧和右侧，则您可以将其旋转直到两个。（在你的图表中或多或少是第一个。）

在这种情况下，您已经知道您已将其放入该一维中（在示例中为 y 轴）。然后，您必须计算另一个维度中内部矩形的边界宽度，并根据外部框的宽度检查它。

可能有一个更智能的算法可以解决这个问题，但我 100% 确定我所描述的内容有效。让我知道您是否可以自己计算出这个数学（如果您认为这是一个很好的解决方案），如果没有，我可能会稍后再试。我想知道我的算法是否可以在没有三角函数的情况下完全实现......

编辑： 好吧，我无法抗拒......

这是我为解决上述问题所做的数学运算：（对不起，仅以图像形式，我希望我的笔迹是可读的。） 如果有人可以检查我的数学，我会很高兴。我现在没有发现任何步骤有任何问题，但最好让其他人检查。（当然：使用这个需要您自担风险。）

如果有人发现此算法有任何问题，请告诉我，我会尽快修复。

我也很想看看是否有人有更好的解决方案，涉及不太复杂的数学。也许是基于向量的方法？

Answer 3

好吧，看起来 ARS 解决方案是正确的，我仍然会尝试发布我的解决方案，这更难，但它会让您将一个矩形具体嵌入到另一个矩形中（如果可能的话）。

让我们假设a>b和p > q。a > p如果和 ，解决方案是显而易见的b > q。a<p如果和也可以解决问题b>q。看看所附的照片，你只需要最后一个不等式系统（如果你有兴趣，你可以看看它是如何推导出来的）

你所需要的只是确保最后一个不等式系统有一个介于0和之间的解1。为此，您需要将每个不等式求解为方程（如通常的二次方程）。如果没有解决方案（这是不可能的），那么不平等的解决方案就是完整的实线。如果方程有两个（可能相等）解t_1，并且t_2不等式的解是[-infinity, t_1]与 结合的部分[t_2, infinity]。在你得到两个不等式的解决方案后，你应该将它们相交。现在我们应该记住t是cos一个角度（在0和之间），所以不等式应该在和pi/2之间有解。在这种情况下，第二个矩形可以嵌入到第一个矩形中。如果你采取例如01t_1（较小的方程根）您可以构建矩形嵌入。

Answer 4

您可以很容易地清除这两个简单的情况：

1. 如果第二个的较大尺寸小于第一个的较大尺寸，并且如果较小的尺寸也是如此，则第二个适合内部。
2. 如果第二个的较大尺寸大于第一个的斜边，那么第二个将不适合第一个。

困难的部分是确定它是否可以以某个角度（例如在您的草图中）适合。我不知道一个简单的公式——它可能需要一个即插即用的解决方案。

可能是数学堆栈交换网站的好问题。

补充： 我不是 100% 确定这是否，但我认为如果第二个的斜边小于第一个的斜边，那么它会合适。

糟糕：不——我会收回它。但是，如果第二个的斜边大于第一个的斜边，它将不适合。