Заливка 3-х мерного полигона - PullRequest
Новая
       24

Заливка 3-х мерного полигона

5 голосов
/ 07 июля 2011

вот вам проблема;)

У меня есть трехмерный массив, заполненный 1 и 0.1 представляют 3-мерные сложные многоугольники (не простые многоугольники).Только границы полигонов имеют значение 1, внутренняя часть заполнена нулями.Теперь вот проблема:

Мне нужен быстрый алгоритм для заполнения этих полигонов 1с.Массивы обычно имеют размер прибл.512x512x100.

Заранее спасибо!

Вот пример в 2d:

0000111110000000010001000000001000100000000111110000

должен привести к

0000111110000000011111000000001111100000000111110000

это правильное трехмерное решение для алгоритма @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

Ответы [ 2 ]

3 голосов
/ 07 июля 2011

Вы можете сделать это в одном цикле 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 et al для вокселизации сетки на GPU. Это не безупречно, так как вы можете иметь конфигурации нескольких немногообразных вершин, где пересекаются шумовые конусы от них, но если вы можете гарантировать, что этого не произойдет (или если это случается редко), это одна из самые простые методы, которые я знаю, чтобы получить быстрый результат.

РЕДАКТИРОВАТЬ: модифицированное решение, чтобы показать, как и массивы обратно вместе после выполнения итерации.

2 голосов
/ 08 июля 2011

Я думаю, что в этом случае можно использовать стандартный подход к заливке: 

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

если вы не уверены, что внутренняя или внешняя части связаны (и, следовательно, невозможно найти единственное «семя»), тогда вы можете выполнять итерацию по всем ячейкам, и как только вы найдете ячейку с нулем затем вы можете вызвать приведенный выше код заливки для вычисления подключенного компонента. Повторяя его для других ячеек, которые будут равны нулю, вы получите все связанные области, в которых грани разделяют пространство.

Конечно, для работы вышеуказанного кода необходимо, чтобы грани были жесткими по отношению к выбранному соединению.

...