algorithm - 立方(洪水)填充

Question

我有一个 3D 数组。在这个数组中，我想找到可以组合成更大元素的元素。矩形不能相互重叠。我最好先找到最大的矩形，但先到先得也不会错，尤其是在提高性能的情况下。

例如

1 0 0 0 1
0 0 0 0 0
0 0 0 0 1
1 1 0 0 1

将产生(因为 3x3 是可以找到的最大矩形；位置 1、0 到 3、2 - zerobased):

0 0 0
0 0 0
0 0 0

和(因为 1x2 是下一个可以找到的最大矩形；位置 0、1 到 0、2):

0
0

和(因为 2x1 是下一个可以找到的最大矩形；位置 2、3 到 3、3):

0 0

当然还有(左边是位置4、1，虽然不大但还是要用)

0

作为更大的元素(我只需要知道零或一)。目的是减少体素网格的碰撞器数量。

我不知道这种算法的名称，也许我可以自己找出如何做到这一点。

如果有人能为此提供一些可行的信息，那就太好了!

Answer 1

对于 2D 情况，用于查找最大矩形的算法是“直方图下的最大矩形区域”。这是一个非常简单的 O(n) 算法，也对此进行了讨论 here .

诀窍是可视化您的矩阵实际上可能被处理为 n 个长度为 m 的直方图 - 在每一行，从上到下，您有一个列高度 0(在您的示例中将由数字 1 表示)，或高度 height[i-1][j] + 1 的列，当当前字符是 0。因此，每行的处理时间为 O(m)，总复杂度为 O(n*m)。现在，由于您想要所有矩形，而不仅仅是最大的矩形，您只需调整算法以“消耗”您满意的任何矩形，也就是说，每当您发现一个杂散的 1中断你的矩形形成，你可以只“消耗”上面那个将被中断的矩形，并确保它下面的其他位置将在高度 0 或 1 重新开始，有效地设置 height[i-1][jbegin~jend ] = 0。 (其中 jbegin 和 jend 是在 i-1 行结束的矩形的开始和结束，您刚刚选择了“使用”，因为它在 i)

行被阻塞

对于 3D 情况，您必须了解直方图算法的工作原理，以便您可以开发自己的适应性，但它​​基本上应该成为上述算法的更复杂版本，跟踪额外的坐标。这可能不是最简单的实现方法，但如果您需要的话，将产生最佳性能。