algorithm - 找到所有可能的矩形放置可能性

Question

以下问题:

假设我们有一个包含多个矩形的矩形 map 。
我想找到所有可能的“最大”矩形，这些矩形可以放置在 map 上而不与任何其他矩形相交。最大的意思是不能在任何方向上放大的矩形。

有人知道执行此任务的算法吗？

enter image description here

Answer 1

我会建议一个可能不是更快但应该可以完成工作的解决方案。

这个想法是一个一个地放置你的每个矩形。每次在 map 中添加一个矩形时，请检查它是否与其他矩形相交。如果是，则根据交叉点的形状将这两个矩形分成正确的相应新矩形。



很容易看出，如果一个新的矩形(绿色)覆盖了整个受影响的矩形(红色)，只有新的矩形会被分开。否则，两者都会。

只需一个一个地添加并正确地将它们分开，您最终将拥有完整的矩形集，您只需要迭代即可找到您的“最大”，如果它意味着面积最大的那些。

这个算法应该是 O(n²) 左右，其中 n 是你添加的矩形的数量。