什么是在最大可能矩形块中返回空闲空间的算法？

Question

算法

考虑这个布局:

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

黑色部分是占用空间.现在我需要一个返回最大剩余矩形空间的算法.(从上到下,从左到右排序.)

像这样:

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

输入

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

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

我正在处理花车,因此数学解决方案将是首选.

Answer 1

从您的示例中可以看出,您并不是要求排除重叠(例如,1和2具有共同的左上角),因此这可能符合您的需求:

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

2. 通过将线段从这些角延伸到整个空间的边缘来形成"基本矩形".

3. 使用任何系统的订单(例如从上到下,从左到右):

   3.1.选择一个基本矩形,并尽可能将其扩展到具有共同侧面的其他基本矩形.

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

请注意,这将根据步骤2中的"基本矩形"进行搜索/构建,而不是在整个空间中逐点进行搜索/构建,因此性能应该更好.