三维多边形的泛洪填充

Question

三维多边形的泛洪填充

c++mathpolygoncomputational-geometryflood-fill

5

这里有一个问题要你解决;)

我有一个填满了1和0的三维数组。1表示三维复杂多边形（不是简单多边形）。只有多边形的边界具有值1，内部填充为0。现在问题在于：

我需要一种快速的算法来将这些多边形进行泛洪填充。这些数组通常具有大约512x512x100的尺寸。

谢谢！

以下是2D示例：

0000111110000
0000100010000
0000100010000
0000111110000

应该得到：

0000111110000
0000111110000
0000111110000
0000111110000

这是@Mikolas算法的正确三维解决方案吗？

    void scan_polygon(int frames, int rows, int cols, char data[][][], char result[][][]){
for(int f=0; f < frames; ++f)
for(int r=0; r<rows; ++r)
for(int s = 0, c=0; c<cols-1; ++c)
{
    s ^= s ? ( data[f][r][c] && !data[f][r][c+1]) :
             (!data[f][r][c] &&  data[f][r][c-1]);

    result[f][r][c] = s;
}

for(int f=0; f < frames; ++f)
for(int c=0; c<cols; ++c)
for(int s = 0, r=0; r<rows-1; ++r)
{
    s ^= s ? ( data[f][r][c] && !data[f][r+1][c]) :
             (!data[f][r][c] &&  data[f][r-1][c]);

    result[f][r][c] &= s;
}

最好的问候，

stef

- stef

当你说“flood-fill”时，是指将整个数组初始化为值1吗？还是只想快速将边界点设置为1，其余部分设置为0？ - Jason

每个数组代表一个多边形吗？ - Jacob

1

我认为他指的是多面体，而不是多边形。如果我理解正确，面的内部都是1，但多面体是“空的”。 - 6502

哇，你们很快。到目前为止，谢谢！ - stef

因为6502正确解读了OP，所以我取消了我的-1。 - Chris Cunningham

显示剩余2条评论

2个回答

2

我认为在这种情况下可以使用标准的洪水填充方法：

active_cells = [seed]
while active_cells:
    new_active_cells = []
    for cell in active_cells:
        for nh in neighbor(cell):
            if not filled(nh):
                fill(nh)
                new_active_cells.append(nh)
    active_cells = new_active_cells

如果你不确定内部或外部是否连接（因此找不到单个“种子”），那么你可以遍历所有单元格，并一旦找到一个零单元格，就可以调用上述泛洪填充代码来计算连接的组件。重复对其他发现为零的单元格执行此操作，最终你将得到所有面在空间中分区的连接区域。

当然，为了使上述代码正常工作，需要选择连通性时面应该是紧密相连的。

- 6502

也许我误解了，但是这不会填充边界外部以及内部的内容吗？ - Chris Cunningham

如果种子点在内部且边界紧密（取决于所使用的连通性定义），那么涂料将无法逃脱该多面体。请注意，这假定一个具有实心面而不仅是边缘的多面体。像我之前所说，仅有边缘时问题并不完整。 - 6502

哦！我完全错过了你在这里的操作，从一个种子开始。由于这是一个复杂的区域，可能有多个“内部”位，他需要先用2或其他东西填充外部，因为我认为外部保证是一个连通区域，然后将所有剩余的0替换为1。顺便加一分。:P - Chris Cunningham

根据拓扑学的不同，甚至“外部”也不一定是连通的。例如考虑一个球体在另一个球体内部的情况... - 6502

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mikola · Accepted Answer

如果您假设多边形是流形的，那么您可以在单个for循环中完成。从左上角开始，穿过边缘时保持奇偶性。

一个简单的2D版本（包括转置案例）：

void scan_polygon(int rows, int cols, char** data, char** result)
{
    for(int r=0; r<rows; ++r)
    for(int s = 0, c=0; c<cols-1; ++c)
    {
        s ^= s ? ( data[r][c] && !data[r][c+1]) :
                 (!data[r][c] &&  data[r][c-1]);

        result[r][c] = s;
    }


    for(int c=0; c<cols; ++c)
    for(int s = 0, r=0; r<rows-1; ++r)
    {
        s ^= s ? ( data[r][c] && !data[r+1][c]) :
                 (!data[r][c] &&  data[r-1][c]);

        result[r][c] &= s;
    }
}

如果您在扫描线上有一个悬挂的像素或边缘，就可能会出现问题，例如：

00000000000000000000        
00000000*11111111111   <--- Whoops!
000000*111*000000000
00000*11111*00000000

为了解决这个问题，您可以在转置数组上重复此过程，然后将所有结果进行AND运算。 Sud等人曾使用类似的方法在GPU上进行网格体素化。这种方法并不完美，因为您可能会有多个非流形顶点的配置，其中它们的嘈杂锥相交，但如果您可以保证不会发生这种情况（或者只是偶尔发生），那么这是我知道的最简单的方法之一，可以快速获得结果。

编辑：修改解决方案以显示如何在迭代后将数组合并。