algorithm - 返回最大可能矩形 block 中可用空间的算法是什么？

Question

算法

考虑这个布局:

+-------------+|             ||             ||   +--+      ||   |##|      ||   |##|      ||   +--+------+|      |######||      |######|+------+------+

黑色部分为占用空间。现在我需要一个算法来返回最大的剩余矩形空间。 (从上到下，从左到右排列。)

像这样:

1                 2          3            4+-------------+   +----      -------+|#############|   |###        ######||#############|   |###        ######||   +--+      |   |###+      +######|                  |###|      |######|                  |###|      |######|                  |###+      +------|     |   +--+                  |###                    |######|                  |###                    |######|                  +----                   +------+

输入

封闭容器的宽度和高度。 (我的代码中的一个页面。)

已占用的矩形列表。它们可以是您喜欢的任何形式。 例如(x,y,width,height) 或 (x1,y1,x2,y2)

我正在处理 float ，因此首选数学解决方案。

Answer 1

从您的示例来看，您似乎并没有要求排除重叠(例如 1 和 2 具有共同的左上段)，所以这也许会满足您的需求:

1. 根据占用空间标识的角将空间划分为矩形。

2. 通过从这些角向整个空间的边缘延伸线段来形成“基本矩形”。

3. 使用任何系统顺序(例如从上到下、从左到右):

   3.1。选择一个基本矩形，并与其他有公共(public)边的基本矩形尽可能远地扩展它。

   3.2。形成所有(唯一的)这样的扩展矩形的集合。

请注意，此搜索/构建基于步骤 2 中的“基本矩形”，而不是在整个空间中逐点搜索，因此性能应该好得多。