检查矩形是否适合已经包含矩形的其他矩形。

Question

我想写一个方法(或类)来检查一个给定的矩形(rectangleToCheck)是否适合另一个(可能)已经包含矩形(innerRectangles)的矩形(extraRectangle)。允许重新排列和旋转（90度）。

public bool CheckIfFits(Rectangle outerRectangle, IEnumerable<Rectangle> innerRectangles, Rectangle rectangleToCheck)
{
}

例如：我已经有了一个简单的部分来检查。

我已经有了一个简单的部分来检查 外角形 的面积之和减去 内矩形 的面积大于或等于 检查的矩形. 但现在我在得到所有可能的自由区域的点，我绝对没有线索，如何计算。

谁能帮帮我？

Answer 1

编辑:两种方法 胜过蛮横递归 存在。

1. "如果你不追求最优化的结果，对贪婪的选择类结果没有意见，你可以将矩形按面积递减排序，然后做如下操作。

从最大的矩形开始填入矩形A每次填入后，都会剩下一些空间，就填入该形状中最大的矩形，如果有任何一个较小的矩形合适，那么就可以重复上一点，否则就用较小的矩形替换最后添加的矩形。做同样的事情，直到你把矩形填满为止.你很有可能把矩形填满，只有在可能的情况下，否则问题不会花太多时间去运行四个较小的矩形。"

2. "为了优化和更好的方法，你可以看看形状退火技术来解决几何knapsack问题。希望对你有所帮助。谢谢。"

https:/www.quora.comI-am-looking-for-algorithms-to-solve-a-geometric-knapsack-problem-It-is-given-figure-A-a-rectangular-with-the-rectangular-holes-You-have-to-give-an-answer-Can-you-build-figure-A-using-a-certain-number-of-smaller-rectangles-B1-B2-B3-B4

关于算法和示例的解释可以在下面的链接中找到，在你的情况下，你需要考虑高度和宽度，而不是重量。 https:/www.geeksforgeeks.org0-1-knapsack-problem-dp-10