Алгоритм Хошена-Копельмана — это простой и эффективный алгоритм маркировки кластеров в сетке, где сетка представляет собой регулярную сеть ячеек, причем ячейки либо заняты, либо незаняты. Этот алгоритм основан на известном алгоритме поиска объединений . [1] Алгоритм был первоначально описан Джозефом Хошеном и Раулем Копельманом в их статье 1976 года «Перколяция и кластерное распределение. I. Метод множественной маркировки кластеров и алгоритм критической концентрации». [2]
Теория перколяции — это изучение поведения и статистики кластеров на решетках . Предположим, у нас есть большая квадратная решетка, где каждая ячейка может быть занята с вероятностью и может быть пустой с вероятностью . Каждая группа соседних занятых ячеек образует кластер. Соседи определяются как ячейки, имеющие общую сторону, но не те, которые имеют общий только угол, т.е. мы рассматриваем 4-связную окрестность : верхнюю, нижнюю, левую и правую. Каждая занятая ячейка не зависит от статуса ее окрестности. Количество кластеров, размер каждого кластера и их распределение являются важными темами теории перколяции. p1 – p
В этом алгоритме мы просматриваем сетку в поисках занятых ячеек и помечаем их метками кластеров. Процесс сканирования называется растровым сканированием . Алгоритм начинается со сканирования ячейки сетки за ячейкой и проверки, занята ячейка или нет. Если ячейка занята, то ее необходимо пометить меткой кластера. Эта метка кластера назначается на основе соседей этой ячейки. (Для этого мы собираемся использовать алгоритм Union-Find , который объясняется в следующем разделе.) Если у ячейки нет занятых соседей, то ячейке присваивается новая метка. [3]
Этот алгоритм представляет собой простой метод вычисления классов эквивалентности . Вызов функции union(x,y)возвращает, являются ли элементы xи yчленами одного и того же класса эквивалентности. Поскольку отношения эквивалентности транзитивны , все элементы, эквивалентные , xэквивалентны всем элементам, эквивалентным y. Таким образом, для любого элемента xсуществует набор элементов, которые все эквивалентны x(называемый классом эквивалентности). Вторая функция find(x)возвращает представительный член класса эквивалентности, к которому он xпринадлежит.
При растровом сканировании сетки всякий раз, когда встречается занятая ячейка, сканируются соседние ячейки, чтобы проверить, не сканировалась ли какая-либо из них уже. Если мы находим уже отсканированных соседей, unionвыполняется операция, чтобы указать, что эти соседние ячейки фактически являются членами одного и того же класса эквивалентности. Затем findвыполняется операция по поиску репрезентативного члена того класса эквивалентности, которым будет помечена текущая ячейка.
С другой стороны, если у текущей ячейки нет соседей, ей присваивается новая, ранее неиспользованная метка. Таким образом обрабатывается вся сетка.