algorithm - 合并和分割重叠的矩形以产生不重叠的矩形

Question

我正在寻找如下算法：

给定一组可能重叠的矩形（所有这些矩形都“不旋转”，可以统一表示为（左、上、右、下）连音等...），它返回一组最小的（非旋转）占据相同区域的非重叠矩形。

乍一看似乎很简单，但事实证明很棘手（至少要有效地完成）。

这个/想法/指针有一些已知的方法吗？

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

Answer 1

我认为基于线扫描算法的东西会起作用：

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

我不完全确定这涵盖了所有内容，但我认为通过一些调整应该可以完成工作。或者至少给你一些想法...... :)

Answer 2

所以，如果我想这样做，我要做的第一件事就是想出一个统一的网格空间。查找所有唯一的 x 和 y 坐标，并创建到索引空间的映射。因此，如果您有 x 值 { -1, 1.5, 3.1 }，则将它们映射到 { 0, 1, 2 }，对于 y 也是如此。然后每个矩形都可以用这些打包的整数坐标精确表示。

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

想出一个非常快速的解决方案的一种方法是转储网格的每个“像素”。通过映射运行它们，你就完成了。如果您正在寻找更优化的矩形数量，那么您手头上就会遇到某种搜索问题。

让我们看看 4 个相邻像素，一个 2x2 的小正方形。当我编写这样的算法时，我通常会考虑顶点、边缘和面。所以，这些是顶点周围的面。如果其中 3 个打开而 1 个关闭，则您有一个凹角。这是唯一无效的情况。例如，如果我没有任何凹角，我只需抓住范围并将整个事物作为单个矩形倾倒。对于每个凹角，您需要决定是水平分割、垂直分割还是两者兼而有之。我认为分割是在查找范围时标记边缘不交叉。您也可以将其作为成套着色来进行，这对您来说更容易。

凹角及其分割方向是您的搜索空间。您可以使用任何您喜欢的优化算法。分支/绑定可能运作良好。我敢打赌，您可以找到一个表现良好的简单启发式方法（例如，如果在您正在考虑的那个直接对面有另一个凹角，则始终沿该方向拆分。否则，沿较短方向拆分）。你可以贪婪。或者你可以在两个方向上分割每个凹形顶点，这通常会给你比将每个“像素”输出为矩形更少的矩形，并且非常简单。

阅读此内容后，我意识到可能存在不清楚的地方。如果你想让我澄清任何事情，请告诉我。