2

给定一个由（白色）矩形和一组（黑色）矩形限制的二维空间占据该空间，我正在寻找一种方法来以某种方式索引空（白色）空间。为此，我想创建一组（白色）矩形，以便对于空间中的任何给定点（不属于任何“黑色”矩形的点），最大的空矩形存在于生成的一组白色矩形中。

谢谢

4

2 回答 2

1

您是在网格中（即图像）还是在连续的 2D 空间中？我的答案是针对每个点都有整数坐标的情况。在另一种情况下，您可以通过我的答案获得近似值。

如果我正确理解你的问题，你需要两件事：

  1. 所有最大空矩形的列表（即只有白点填充的矩形，在不包括黑点的情况下不能在任何方向上扩展）（也称为“最大空矩形”，或文献中的 MER）。
  2. 矩形指针的 2D 数组，对于每个点，指示包含该点的最大空矩形。其他数据结构也是可能的，但我不会描述它们，因为选择主要取决于您的目标应用程序要求。

为了计算列表，您可以使用算法 O(N)，其中 N 是黑白图像中的像素数量。您可以在http://www.ulg.ac.be/telecom/rectangles找到描述这种算法的论文，其中包含一些（未优化的）C++ 源代码。在实践中，它非常快。

为了计算 pinters 的 2D 数组，您需要遍历所有最大空矩形的列表，并为每个空矩形更新所有包含像素的指针（如有必要）。由于最多有 N 个最大的空矩形（有关 prorof，请参阅http://www.ulg.ac.be/telecom/rectangles上链接的论文），并且每个矩形包含最多 N 个像素，这一步是最差的情况 O(N^2)。不知道能不能降低这一步的成本。

于 2013-07-09T14:06:42.497 回答
0

http://rd.springer.com/chapter/10.1007%2F3-540-53487-3_50 本文描述了一种有效的方法来解决我的问题。

问候， 达姆扬

于 2013-07-15T15:15:29.730 回答