Блог

У меня есть 3D «кубическая» матрица, в которой некоторые ячейки заполнены, а другие пусты. Замкнутая область, окруженная заполненными ячейками, представляет собой полую форму. Например, в матрице ячейки могут быть заполнены таким образом, что вместе они образуют поверхность полой сферы. Теперь мне нужен эффективный способ заполнить внутреннюю часть этой сферы: если ячейка C0 окружена во всех направлениях заполненными ячейками (заполненная ячейка в любом направлении не обязательно должна быть ближайшим соседом C0 ), затем заполните C0 .

Наивный способ был бы следующим :-

Для каждой ячейки сканируйте в направлении X, -X, Y, -Y, Z, -Z и посмотрите, не встретите ли вы заполненную ячейку в каждом направлении.

Если заполненная ячейка встречается в каждом направлении, затем заполните эту ячейку (поскольку она является частью внутренней части некоторой фигуры).

Если вы дойдете до конца сетки даже в одном направлении, не встретив ни одной заполненной ячейки, то рассматриваемая ячейка не является внутренней для какой-либо формы и должна оставаться незаполненной.

Сложность вышеуказанного подхода заключается O(n^4) в том, где размерность 3D-сетки n*n*n .

Оптимизация может заключаться в следующем :-

Если для незаполненной ячейки C [x] [y] [z] мы обнаружили по одной заполненной ячейке во всех 6 направлениях, то необходимо заполнить не только C [x] [y] [z], также гарантируется, что все ячейки, которые мы только что отсканировали (т.е. {в направлении X все ячейки C [x] [y] [z], C [x 1] [y] [z], C [x 2] [y] [z], …, до первой заполненной ячейки}, аналогично для -X,Направление Y, -Y, Z, -Z) должно быть частью внутренней части некоторой формы и, следовательно, должно быть заполнено.

Другой может быть следующим :-

Если для незаполненной ячейки C [x] [y] [z] мы НЕ встретим ни одной заполненной ячейки, скажем, в направлении X, то мало того, что C [x] [y] [z] останется незаполненным, также гарантируется, что все ячейки, которые мы сканировали, простотеперь (т.е. в направлении X, все ячейки C [x] [y] [z], C [x 1] [y] [z], C [x 2] [y] [z], …, до конца сетки) должны быть частьювнешний и, следовательно, должен оставаться незаполненным.

Может кто-нибудь предложить более эффективный подход к этой проблеме? Приветствуются даже простые оптимизации, подобные приведенным выше, которые могут не уменьшить порядок временной сложности.

Вы имеете дело с 3D заливкой. Смотрите подробную статью в Википедии http://en.m.wikipedia.org/wiki/Flood_fill

Хорошо, поскольку это закрытые пустотелые формы, мы можем просто использовать BFS или DFS для решения проблемы.

BFS:

Начиная с пустой очереди, добавьте в очередь любую ячейку, которая находится внутри полой формы. Из верхней части очереди извлеките одну ячейку, заполните эту ячейку и проверьте 6 других соседей этой ячейки, если этот сосед не заполнен, добавьте его в очередь, иначе просто игнорируйте эту ячейку. Продолжайте этот процесс, пока очередь не опустеет.

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

Временная сложность равна O (количество необходимых для заполнения ячеек * необходимо проверить направление 6)

Подсказка для перехода в 6 направлении:

 int[] x = {0,0,0,0,1,-1};
int[] y = {0,0,1,-1,0,0};
int[] z = {1,-1,0,0,0,0};

Point p = // point in space with three dimension x,y,z

for(int i = 0; i < 6; i  ){
     int a = p.x   x[i];
     int b = p.y   y[i];
     int c = p.z   z[i];
}
  

Для каждой ячейки сканируйте в направлении X, -X, Y, -Y, Z, -Z и посмотрите, не встретите ли вы заполненную ячейку в каждом направлении.

Если заполненная ячейка встречается в каждом направлении, затем заполните эту ячейку (поскольку она является частью внутренней части некоторой фигуры).

Приведенное выше утверждение неверно, если вы не имеете дело только с выпуклыми оболочками. На изображении ниже показано, что рассматриваемая точка не заключена в синюю фигуру, но она все равно будет пересекаться во всех направлениях (x, y, z).

Вместо этого, чтобы справиться с общим случаем поиска полых фигур, вы можете добавить все ячейки в набор. Затем начните с граничной ячейки. Ячейка на границе является частью полой формы, если она заполнена, в противном случае она является частью фоновой (незаполненной) формы.

Затем, подобно ответу @Pham Trung, вы можете перемещаться наружу во всех направлениях, пока не пройдете все ячейки, которые находятся внутри фигуры, игнорируя цветные ячейки на границах. Выберите другую ячейку на границе предыдущей фигуры и начните процесс заново, пока не будут пройдены все ячейки.

В итоге каждая ячейка будет помечена либо как часть полой формы, либо как фон.

Просто для полноты, еще два. YMMV зависит от множества факторов.

1. Найдите поверхность

Если вы имеете дело с большим количеством вокселов, одной из возможностей оптимизации было бы найти граничную поверхность углубления. Это можно сделать, как в ответе Фама Трунга, но принимать только ячейки, в которых заполнен хотя бы один из их 6 соседей.

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

Этот метод позволяет значительно уменьшить размер набора, если у вас большое количество вокселов (масштабируется как n ^ 2 вместо n ^ 3). Поиск набора обычно выполняется очень быстро, но если набор не помещается в оперативную память, он сильно замедляется.

2. Срез до 2D

Другой возможностью было бы нарезать фигуру на 2D-фрагменты и соединить полученные полости слой за слоем. Тогда в памяти одновременно должны храниться только два фрагмента.

Основная идея состоит в том, чтобы присвоить каждой отдельной связанной 2D-области собственный идентификатор, а затем найти ее соединения с уже известными областями в соседнем слое. После обработки всех слоев остаются связанные 3D-области.

Сложной задачей является поиск наилучшего алгоритма для соединения 2D-областей в соседних слоях. Кажется, что этот метод работает быстро с простыми формами (несколько несвязанных областей в 2D-срезах), но медленно со сложными формами («червоточины в дереве»). Кроме того, необходим быстрый алгоритм для поиска одной общей точки в двух наборах. (Т.е. Полное пересечение множеств не требуется, только информация о том, имеют ли множества хотя бы одну общую точку или нет.)

Опять же, если ваши наборы имеют разумный размер, тривиальный алгоритм, описанный Pham Trung, вероятно, является лучшим выбором.