5

here is a problem for you ;)

I have a 3-dimensional array filled with 1s and 0s. The 1s represent 3 dimensional complex polygons ( not simple polygons ). Only the boundaries of the polygons have the value 1, the inside is filled with 0s. Now here is the problem:

I need a fast algorithm to flood-fill these polygons with 1s. The arrays usually have a dimension of approx. 512x512x100.

Thanks in advance!

Here is an example in 2d:

0000111110000
0000100010000
0000100010000
0000111110000

should result in

0000111110000
0000111110000
0000111110000
0000111110000

is this the correct 3 dimensional solution for @Mikolas algorithm?

    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;
}

}

Best regards,

stef

4

2 回答 2

3

如果您假设您的多边形是多方面的，您可以在单个 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

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

编辑：修改后的解决方案以显示如何在迭代后将数组重新组合在一起。

于 2011-07-07T19:53:34.957 回答
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

如果您不确定内部或外部是否连接（因此无法找到单个“种子”），那么您可以做的是遍历所有单元格，一旦找到一个为零的单元格，那么您可以调用上面的 floodfill 代码来计算连通分量。对其他发现为零的单元格重复此操作，您最终将得到所有连接区域，这些区域将面划分为空间。

当然，要使上述代码正常工作，就要求面相对于所选的连接性而言是紧密的。

于 2011-07-07T20:01:33.173 回答