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

    sergiks
    @sergiks Куратор тега Алгоритмы
    ♬♬
    Вроде бы, тут почти нечего читать по теме.
    Представьте кубик Рубика 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, алгоритм маппинга координат в одномерный массив и оптимизация – на вашей совести.
    Ответ написан
    3 комментария