2

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

红色矩形可能重叠。

4

4 回答 4

2

这是一个分而治之的算法；这个想法与快速排序大体相似。我假设矩形不重叠，并且它们都包含在边界框中，尽管边界可能会接触。

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

每个矩形最多可以参与 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))

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

例子

如果最小化矩形的数量很重要，您可能需要考虑“上”、“左”、“右”和“下”的不同边界框，并再次检查结果以将任何矩形连接在一起（如果它们有）相等的两条边为线段。

于 2020-03-03T15:46:28.903 回答
1

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

  • y获取位于红色矩形开头或结尾的所有 s 的排序列表。
  • 在列表的开头添加 0，在列表末尾添加总高度。
  • 对于每个 ( y1, y2) 区间：
    • y1检查哪些红色矩形在和之间的水平带中，按坐标y2排序x
    • 创建左坐标和右坐标的排序列表：left_list[i]将包含第 i 个矩形的左边界（类似于right_list）。添加 0 作为第一个元素right_list和总宽度作为最后一个元素left_list
    • 对于所有 i，在 x 和 y 之间和right_list[i]y之间创建一个绿色矩形。left_list[i]y1y2
于 2020-03-03T14:50:21.640 回答
1

最简单的解决方案如下。

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

xlist对 和 中的重复项进行排序和删除ylist。

对于每两个相邻元素x1, x2inxlist和每两个相邻元素y1, y2in ylist（两个嵌套循环） ，使用坐标, ,for创建一个新的绿色矩形（除非新的绿色矩形与任何红色矩形重叠）。x1x2y1y2

这将为您提供比必要更多的绿色矩形，但您没有给出任何限制，所以就这样;）

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

于 2020-03-03T15:23:00.133 回答
-1

从图中可以看出，矩形 A 填充了红色矩形 1 上方的所有空间。

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

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

矩形 D 被两个红色矩形包围。

矩形 E - G 填充剩余空间（顶部、右侧、底部）。

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

于 2020-03-03T14:49:35.303 回答