我如何获得可以填充 space *不包括*其他一些矩形的矩形？
How do I get the rectangles which would fill out a space *excluding* some other rectangles?
标题说明了一切。例如：
给定红色矩形，我想得到所有绿色矩形。
我知道边界矩形的大小。
红色矩形可能重叠。
从图中可以看出，矩形A填满了红色矩形1上方的所有space。
矩形 B 填充红色矩形 1 左侧的所有 space。
矩形 C 填充红色矩形 1 右侧的所有 space。
矩形 D 由两个红色矩形包围。
矩形 E - G 填充 space 的剩余部分（顶部、右侧、底部）。
算法似乎是，取每个红色矩形并填充它周围的 space。除非有其他限制，否则好像是这个过程。
为绿色矩形提供一种可能性的解决方案，不一定与图片中的相同，也不总是矩形数量最少的那个：
- 获取位于红色矩形开始或结束处的所有
y 的排序列表。
- 在开头加0，在列表末尾加总高度。
- 对于每个 (
y1, y2) 间隔：
- 检查哪些红色矩形在
y1 和 y2 之间的水平带中，按 x 坐标 对它们进行排序
- 创建左坐标和右坐标的排序列表：
left_list[i] 将包含第 i 个矩形的左边界（与 right_list 类似）。添加 0 作为 right_list 的第一个元素和总宽度作为 left_list 的最后一个元素
- 对于所有 i，在 x 上的
right_list[i] 和 left_list[i] 之间以及 y 上的 y1 和 y2 之间创建一个绿色矩形。
最简单的解决方法如下。
创建两个列表 xlist 和 ylist，对于每个红色矩形及其每个角，将该点的 x 坐标插入 xlist 和 y坐标变成ylist。对边界框执行相同操作。
排序并删除 xlist 和 ylist 中的重复项。
对于xlist中的每两个相邻元素x1、x2和ylist中的每两个相邻元素y1、y2(两个嵌套的 for 循环），使用坐标 x1、x2、y1、y2 创建一个新的绿色矩形（除非新的绿色矩形与任何红色矩形）。
这会给你更多的绿色矩形，但你没有给出任何限制，所以就这样吧;)
如果您想限制矩形的数量，可以轻松地将相邻的绿色矩形合并成一行。
这是一个分而治之的算法；这个想法与 quicksort 大致相似。我假设矩形不重叠，并且它们都包含在边界框内，尽管边界可能会接触。
- 如果边界框退化（即零宽度或零高度），则什么也不做。
- 否则如果没有矩形，则只生成边界框本身。
- 否则：
- 从列表中选择一个矩形作为"pivot"。
- 为 "above"、"left"、"right" 和 "below" 枢轴创建新的边界框。
- 构建矩形列表 "above"、"left"、"right" 和 "below" 通过过滤与每个新边界框相交的矩形列表并剪裁它们到边界框。
- 递归地细分 "above"、"left"、"right" 和 "below" 边界框，分别按其中的新矩形列表。
每个矩形最多可以参与4次递归调用中的2次。如果枢轴是随机选择的，并且大多数矩形不与大多数其他矩形垂直重叠，则平均每个矩形都涉及一次递归调用。由于非递归工作需要线性时间，因此在这种情况下预期的 运行 时间为 O(n log n)，其中 n 是矩形的数量。
Python中的实现：
import random
from collections import namedtuple
Rectangle = namedtuple('Rectangle', 'x1 y1 x2 y2')
def intersects(b, r):
return b.x1 < r.x2 and b.x2 > r.x1 and b.y1 < r.y2 and b.y2 > r.y1
def clip_rect(b, r):
return Rectangle(
max(b.x1, r.x1), max(b.y1, r.y1),
min(b.x2, r.x2), min(b.y2, r.y2)
)
def clip_rects(b, rects):
return [clip_rect(b, r) for r in rects if intersects(b, r)]
def split_rectangles(b, rects):
if b.x1 >= b.x2 or b.y1 >= b.y2:
pass
elif not rects:
yield b
else:
# randomize to avoid O(n^2) runtime in typical cases
# change this if deterministic behaviour is required
pivot = random.choice(rects)
above = Rectangle(b.x1, b.y1, b.x2, pivot.y1)
left = Rectangle(b.x1, pivot.y1, pivot.x1, pivot.y2)
right = Rectangle(pivot.x2, pivot.y1, b.x2, pivot.y2)
below = Rectangle(b.x1, pivot.y2, b.x2, b.y2)
yield from split_rectangles(above, clip_rects(above, rects))
yield from split_rectangles(left, clip_rects(left, rects))
yield from split_rectangles(right, clip_rects(right, rects))
yield from split_rectangles(below, clip_rects(below, rects))
示例：如您所见，它没有使用最小数量的矩形，因为右侧有两个可以垂直连接在一起的矩形。
如果最小化矩形的数量很重要，您需要考虑 "above"、"left"、"right" 和 "below" 的不同边界框，然后执行第二次传递结果以将任何矩形连接在一起，如果它们的两条边与线段相等。
标题说明了一切。例如：
红色矩形可能重叠。
从图中可以看出，矩形A填满了红色矩形1上方的所有space。
矩形 B 填充红色矩形 1 左侧的所有 space。
矩形 C 填充红色矩形 1 右侧的所有 space。
矩形 D 由两个红色矩形包围。
矩形 E - G 填充 space 的剩余部分（顶部、右侧、底部）。
算法似乎是，取每个红色矩形并填充它周围的 space。除非有其他限制，否则好像是这个过程。
为绿色矩形提供一种可能性的解决方案，不一定与图片中的相同，也不总是矩形数量最少的那个：
- 获取位于红色矩形开始或结束处的所有
y的排序列表。 - 在开头加0，在列表末尾加总高度。
- 对于每个 (
y1,y2) 间隔：- 检查哪些红色矩形在
y1和y2之间的水平带中，按x坐标 对它们进行排序
- 创建左坐标和右坐标的排序列表：
left_list[i]将包含第 i 个矩形的左边界（与right_list类似）。添加 0 作为right_list的第一个元素和总宽度作为left_list 的最后一个元素
- 对于所有 i，在 x 上的
right_list[i]和left_list[i]之间以及 y 上的y1和y2之间创建一个绿色矩形。
- 检查哪些红色矩形在
最简单的解决方法如下。
创建两个列表 xlist 和 ylist，对于每个红色矩形及其每个角，将该点的 x 坐标插入 xlist 和 y坐标变成ylist。对边界框执行相同操作。
排序并删除 xlist 和 ylist 中的重复项。
对于xlist中的每两个相邻元素x1、x2和ylist中的每两个相邻元素y1、y2(两个嵌套的 for 循环），使用坐标 x1、x2、y1、y2 创建一个新的绿色矩形（除非新的绿色矩形与任何红色矩形）。
这会给你更多的绿色矩形，但你没有给出任何限制，所以就这样吧;)
如果您想限制矩形的数量，可以轻松地将相邻的绿色矩形合并成一行。
这是一个分而治之的算法；这个想法与 quicksort 大致相似。我假设矩形不重叠，并且它们都包含在边界框内，尽管边界可能会接触。
- 如果边界框退化（即零宽度或零高度），则什么也不做。
- 否则如果没有矩形，则只生成边界框本身。
- 否则：
- 从列表中选择一个矩形作为"pivot"。
- 为 "above"、"left"、"right" 和 "below" 枢轴创建新的边界框。
- 构建矩形列表 "above"、"left"、"right" 和 "below" 通过过滤与每个新边界框相交的矩形列表并剪裁它们到边界框。
- 递归地细分 "above"、"left"、"right" 和 "below" 边界框，分别按其中的新矩形列表。
每个矩形最多可以参与4次递归调用中的2次。如果枢轴是随机选择的，并且大多数矩形不与大多数其他矩形垂直重叠，则平均每个矩形都涉及一次递归调用。由于非递归工作需要线性时间，因此在这种情况下预期的 运行 时间为 O(n log n)，其中 n 是矩形的数量。
Python中的实现：
import random
from collections import namedtuple
Rectangle = namedtuple('Rectangle', 'x1 y1 x2 y2')
def intersects(b, r):
return b.x1 < r.x2 and b.x2 > r.x1 and b.y1 < r.y2 and b.y2 > r.y1
def clip_rect(b, r):
return Rectangle(
max(b.x1, r.x1), max(b.y1, r.y1),
min(b.x2, r.x2), min(b.y2, r.y2)
)
def clip_rects(b, rects):
return [clip_rect(b, r) for r in rects if intersects(b, r)]
def split_rectangles(b, rects):
if b.x1 >= b.x2 or b.y1 >= b.y2:
pass
elif not rects:
yield b
else:
# randomize to avoid O(n^2) runtime in typical cases
# change this if deterministic behaviour is required
pivot = random.choice(rects)
above = Rectangle(b.x1, b.y1, b.x2, pivot.y1)
left = Rectangle(b.x1, pivot.y1, pivot.x1, pivot.y2)
right = Rectangle(pivot.x2, pivot.y1, b.x2, pivot.y2)
below = Rectangle(b.x1, pivot.y2, b.x2, b.y2)
yield from split_rectangles(above, clip_rects(above, rects))
yield from split_rectangles(left, clip_rects(left, rects))
yield from split_rectangles(right, clip_rects(right, rects))
yield from split_rectangles(below, clip_rects(below, rects))
示例：如您所见，它没有使用最小数量的矩形，因为右侧有两个可以垂直连接在一起的矩形。
如果最小化矩形的数量很重要，您需要考虑 "above"、"left"、"right" 和 "below" 的不同边界框，然后执行第二次传递结果以将任何矩形连接在一起，如果它们的两条边与线段相等。