我如何获得将填充一个空格的矩形，但不包括其他一些矩形？

Question

标题说明了一切。例如：给定红色矩形，我想获取所有绿色矩形。我知道边界矩形的大小。

红色矩形可能重叠。

Answer 1

一种为您提供绿色矩形的解决方案，不一定与图片中的绿色相同，也不一定总是矩形数量最少的一种：

• 获取在红色矩形的开始或结尾处的所有y的排序列表。
• 在列表的开头加0，在列表的末尾加总高度。
• 对于每个（y1，y2）间隔：
  • 检查哪些红色矩形位于y1和y2之间的水平带中，并按x坐标对其进行排序
  • [在x的right_i和left_i + 1之间以及y的y1和y2之间创建一个绿色矩形。

Answer 2

最简单的解决方案如下。

为每个红色矩形及其每个角创建两个列表xlist和ylist，将该点的x坐标插入xlist，将y坐标插入ylist。对边界框执行相同的操作。

从xlist和ylist中排序并删除重复项。

[对于x1中的每两个相邻元素x2，xlist和y1中的每两个相邻元素y2，ylist（两个嵌套的for循环），请使用坐标x1，x2，y1，y2（除非新的绿色矩形与任何红色矩形重叠）。

这将为您提供更多的绿色矩形，但是您没有给出任何限制，所以这里就来了；）

如果您想限制矩形的数量，可以轻松地将相邻的绿色矩形合并为一行。

Answer 3

这里是分治法；这个想法大致类似于quicksort。我假设这些矩形不重叠，并且它们都包含在边界框中，尽管边界可能会碰到。

• 如果边界框是退化的（即零宽度或零高度），则什么都不做。
• 否则，如果没有矩形，则只产生边界框本身。
• 否则：
  • 从列表中选择一个矩形作为“枢轴”。
  • 为枢轴的“上方”，“左侧”，“右侧”和“下方”创建新的边界框。
  • 通过过滤与每个新边界框相交的矩形的列表并将其剪切到边界框，来构建枢轴“上方”，“左侧”，“右侧”和“下方”的矩形列表。
  • 通过分别在其中的矩形的新列表分别递归地将“上方”，“左侧”，“右侧”和“下方”边界框细分。

每个矩形最多可以参与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 not rects:
        yield b
    elif b.x1 < b.x2 and b.y1 < b.y2:
        # 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))

示例：如您所见，它没有使用最小数量的矩形，因为右侧有两个可以垂直连接在一起的矩形。

如果最小化矩形的数量很重要，则您需要考虑“上方”，“左侧”，“右侧”和“下方”的不同边界框，然后对结果进行第二次传递以将所有矩形连接在一起，如果它们的两侧等于线段。

Answer 4

从图片中看起来矩形A填充了红色矩形1上方的所有空间。

矩形B填充红色矩形1左侧的所有空间。

矩形C填充红色矩形1右侧的所有空间。

矩形D由两个红色矩形绑定。

矩形E-G填充空间的其余部分（顶部，右侧，底部）。

该算法似乎是，取每个红色矩形并填充其周围的空间。除非有其他限制，否则似乎就是这个过程。