4

我正在寻找如下算法:

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

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

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

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

4

2 回答 2

8

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

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

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

于 2010-05-02T23:49:31.007 回答
1

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

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

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

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

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

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

于 2010-05-03T22:47:36.437 回答