合并和拆分重叠的矩形以生成不重叠的矩形

Question

我正在寻找以下算法：

给定一组可能重叠的矩形（所有矩形都是“未旋转”的，可以统一表示为（左，上，右，下）四元组等），它返回一组最小的（未旋转的）不重叠矩形，它们占据相同的区域。

乍一看似乎很简单，但实际上很棘手（至少要高效地完成）。

是否有一些已知的方法/思路/指针？

不一定是最小集合的方法，但启发式小集合的方法也很有趣，产生任何有效输出集合的方法也很有趣。

- uj2

---

你的意思是将矩形取并集并将其分割成矩形区域吗？还是必须在输出中表达原始线条的并集？换句话说，如果我有两个相邻的10x20矩形，我能输出一个20x20的正方形吗？还是说如果我有两个输入，我总是需要至少两个输出？ - tfinniga

输出集合（并集）的唯一要求是占据与输入集合（并集）相同的区域，并由不重叠的矩形组成。最好它也是最小的：包含尽可能少的矩形。因此，在这种情况下最好输出一个单独的矩形。 - uj2

你使用的编程语言是什么？ - tfinniga

如果将来有人出现 - https://dev59.com/vW025IYBdhLWcg3wl3Am 是一个重复的问题，并且在答案中有最优和有效的解决方案。 - Julian

@Julian - 那个问题不是这个问题的重复，因为那个问题明确表示没有重叠的矩形，而这个问题则明确有。解决方案似乎也期望输入数据的不同布局。 - Tustin2121

Answer 1

我认为基于线性扫描算法的某些方法可以解决这个问题：

• 将所有矩形的最小和最大x坐标按顺序排列成一个数组，作为“开始矩形”和“结束矩形”事件。
• 遍历该数组，并将遇到的每个新矩形（开始事件）添加到当前集合中。
• 同时，维护一组“不重叠矩形”，这将是输出集。
• 每当您遇到新矩形时，都可以检查它是否已完全包含在当前/输出集中（简单比较y坐标即可）。
• 如果没有，请添加一个新矩形到输出集中，其中y坐标设置为尚未覆盖的新矩形的部分。
• 每当您遇到矩形结束事件时，请停止不再覆盖任何内容的输出集中的任何矩形。

我不完全确定这是否涵盖了所有情况，但我认为通过一些调整应该可以解决问题。或者至少给你一些想法… :)

- tzaman

---

这条评论为我带来了一些好的想法，我已经完成了大部分实现，但在一些边缘情况下遇到了麻烦。你能详细说明一下结束事件的情况吗？一个矩形“不再覆盖任何东西”是什么意思？ - schellsan

@schellsan - 想象一条垂直线在输入集合（-x到+x）上从左到右扫过。当你碰到任何输入矩形的起点时，你需要创建一个新的输出矩形来覆盖它，除非它已经被你现有的输出矩形完全覆盖。当你到达任何输入矩形的末尾时，如果该空间中没有其他输入矩形（y坐标），则需要结束某些输出矩形（并根据输入配置可能创建一些新的矩形）。 - tzaman

是的，这就是我想到的。谢谢你的帮助！ - schellsan

Answer 2

所以，如果我试图做这件事，第一件事是想出一个统一的网格空间。找到所有独特的x和y坐标，并创建一个映射到索引空间的映射。因此，如果您有x值{-1、1.5、3.1}，则将其映射到{0、1、2}，y也是如此。然后每个矩形都可以用这些紧密打包的整数坐标准确地表示。

然后，我会分配一个位向量或覆盖整个网格的其他内容，并在网格中光栅化您的矩形。拥有网格的好处是它非常容易使用，并且通过将其限制为唯一的x和y坐标，它是最小和精确的。

想要快速找到解决方案的一种方法就是将网格的每个'像素'全部转储..再通过映射运行它们，然后你就完成了。如果您正在寻找更优化的矩形数量，则需要处理某种搜索问题。

让我们看一下4个相邻的像素，一个小的2x2正方形。当我编写这样的算法时，通常我会从顶点、边缘和面的角度考虑。所以，这些是围绕着一个顶点的面。如果其中3个打开了，1个关闭了，那么你就有了一个凹角。这是唯一的无效情况。例如，如果我没有任何凹角，我只需抓取范围并将整个内容作为单个矩形转储即可。对于每个凹角，您需要决定是水平分割、垂直分割还是两者都要。我认为分割是标记不要跨越的边缘，以便找到范围。您也可以将其彩色分组，以便更容易处理。

凹角及其分割方向是您的搜索空间...您可以使用任何优化算法。分支/界限可能效果很好。我敢打赌，您可以找到一个简单的启发式算法（例如，如果在您正在考虑的凹角的正对面有另一个凹角，则始终朝那个方向分割。否则，朝较短的方向分割）。您可以采用贪心策略。或者您可以在两个方向上分割每个凹角，这通常会给您比将每个“像素”输出为矩形更少的矩形，并且非常简单。

阅读这篇文章时，我意识到可能有一些不清楚的地方。如果您需要我澄清任何问题，请让我知道。

- tfinniga