我正在寻找如下算法:
给定一组可能重叠的矩形(所有这些矩形都“不旋转”,可以统一表示为(左、上、右、下)连音等...),它返回一组最小的(非旋转)占据相同区域的非重叠矩形。
乍一看似乎很简单,但事实证明很棘手(至少要有效地完成)。
这个/想法/指针有一些已知的方法吗?
不一定是最小但启发式小集的方法也很有趣,产生任何有效输出集的方法也很有趣。
我正在寻找如下算法:
给定一组可能重叠的矩形(所有这些矩形都“不旋转”,可以统一表示为(左、上、右、下)连音等...),它返回一组最小的(非旋转)占据相同区域的非重叠矩形。
乍一看似乎很简单,但事实证明很棘手(至少要有效地完成)。
这个/想法/指针有一些已知的方法吗?
不一定是最小但启发式小集的方法也很有趣,产生任何有效输出集的方法也很有趣。
我认为基于线扫描算法的东西会起作用:
x
坐标排序到一个数组中,作为“开始矩形”和“结束矩形”事件y
-coordinates 比较就足够了)y
-coordinates 设置为新矩形中尚未覆盖的部分。我不完全确定这涵盖了所有内容,但我认为通过一些调整应该可以完成工作。或者至少给你一些想法...... :)
所以,如果我想这样做,我要做的第一件事就是想出一个统一的网格空间。查找所有唯一的 x 和 y 坐标,并创建到索引空间的映射。因此,如果您有 x 值 { -1, 1.5, 3.1 },则将它们映射到 { 0, 1, 2 },对于 y 也是如此。然后每个矩形都可以用这些打包的整数坐标精确表示。
然后我会分配一个位向量或覆盖整个网格的东西,并在网格中光栅化你的矩形。拥有网格的好处是它非常易于使用,并且通过将其限制为唯一的 x 和 y 坐标,它是最小且精确的。
想出一个非常快速的解决方案的一种方法是转储网格的每个“像素”。通过映射运行它们,你就完成了。如果您正在寻找更优化的矩形数量,那么您手头上就会遇到某种搜索问题。
让我们看看 4 个相邻像素,一个 2x2 的小正方形。当我编写这样的算法时,我通常会考虑顶点、边缘和面。所以,这些是顶点周围的面。如果其中 3 个打开而 1 个关闭,则您有一个凹角。这是唯一无效的情况。例如,如果我没有任何凹角,我只需抓住范围并将整个事物作为单个矩形倾倒。对于每个凹角,您需要决定是水平分割、垂直分割还是两者兼而有之。我认为分割是在查找范围时标记边缘不交叉。您也可以将其作为成套着色来进行,这对您来说更容易。
凹角及其分割方向是您的搜索空间。您可以使用任何您喜欢的优化算法。分支/绑定可能运作良好。我敢打赌,您可以找到一个表现良好的简单启发式方法(例如,如果在您正在考虑的那个直接对面有另一个凹角,则始终沿该方向拆分。否则,沿较短方向拆分)。你可以贪婪。或者你可以在两个方向上分割每个凹形顶点,这通常会给你比将每个“像素”输出为矩形更少的矩形,并且非常简单。
阅读此内容后,我意识到可能存在不清楚的地方。如果你想让我澄清任何事情,请告诉我。