Как найти связные области в 3D?

Question

[dride]

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


Задача:

Имеется куб целочисленных данных (куб признаков 0 или 1). Отдельные элементы куба будем называть ячейками. Размеры куба заданы (в направлении I: Nx элементов, в направлении J: Ny, в направлении K: Nz). Куб хранится в одномерном массиве (размером Nx*Ny*Nz), данные в нем уложены в следующем порядке: вначале меняется индекс I, потом меняется индекс J, затем меняется индекс K.

Пример такого куба надо сделать самостоятельно, заполнить его случайным образом. Размер куба взять ориентировочно 100 млн. чисел (в реальных задачах могут быть и миллиарды чисел, скорость расчетов очень критична) - например, куб 400*250*100.

Требуется найти связанные между собой 3D области внутри куба (количество таких областей и номера ячеек, которые в них содержатся). Например, Область №1 (ячейки 100, 101 ... - нумерация сквозная по одномерному массиву), Область №2

Answer 1

[Сергей Соколов]

Вроде бы, тут почти нечего читать по теме.
Представьте кубик Рубика 3х3х3 со всеми внутренними кубиками.
Каждый кубик это 1 или 0.

Надо найти индексы связанных областей ("островов") из единичек.

на пальцах

Для плоского 2D и размера 5х5 например это могло бы выглядеть так:

YX| 0 1 2 3 4
--|-----------
0 | 0 1 0 0 1
1 | 1 1 0 1 1
2 | 1 0 1 1 0
3 | 0 1 1 0 0
4 | 0 0 1 0 0

Ячейки считать связанными, если не по диагонали, а точно сверху, снизу, справа или слева есть еще одна с 1. На примере выше две области связанны (нумерация слева направо и сверху вниз):

[(1,0), (0,1), (1,1), (0,2)],
[(4,0), (3,1), (4,1), (2,2), (3,2), (1,3), (2,3), (2,4)]

В 3D добавляется третье измерение, третья ось для поиска соседей, третья координата.

Про двухмерный поиск связных областей на Хабре.
Адаптация к 3D, алгоритм маппинга координат в одномерный массив и оптимизация – на вашей совести.

Comments

[dride]

Если это настолько просто, а я не врубился без помощи, то возникают большие вопросы к моим способностям в программировании...

[Сергей Соколов]

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

[dride]

Сергей Соколов, спасибо за потраченное время и помощь.