Find groups of contiguous cells in a 3D binary matrix

Question

I want to find groups of contiguous cells in a matrix.

So for example let’s consider a 2D matrix below.

In the given matrix there are 2 contiguous groups of cells with value 1:

Here is one way to find these groups:

1. Assign 1st cell with value 1 a different value: let’s say A. Then examine cells with value 1 which are adjacent to A and set the value in those cells as A. Search this way until no more contiguous cells are found.

2. In the next step increment A to B and start with a cell having value 1. Then follow the same steps as above.

This is kind of brute force and it won’t be efficient in 3D. Does anyone know of any algorithm that I could use with a little tweaking?

Or any easy solution to this problem?

Answer 1

What you are trying to do goes, often, under the label connected component labelling. I won't elaborate further, the Wikipedia article explains matters better than I could or would.

But while I'm answering ...

You, and many others on SO, seem to think that simple iteration over all the elements of an array, which you characterise by the derogatory term brute-force, is something to be avoided at all costs. Modern computers are very, very fast. Accessing each element of an array in order is something that most compilers can optimise the hell out of.

You seem to have fallen into the trap of thinking that accessing every element of a 3D array has time-complexity in O(n^3), where n is the number of elements along each dimension of the array. It isn't: accessing elements of an array is in O(n) where n is the number of elements in the array.

Even if the time complexity of visiting each element in the array were in O(n^3) many sophisticated algorithms which offer better asymptotic time complexity, will prove, in practice, to deliver worse performance than the simpler algorithm. Many sophisticated algorithms make it much harder for the compiler to optimise code. And, bear in mind, that O(n^2) is an equivalence class of algorithms which includes algorithms with true time complexities such as O(m+k*n^2) where both of m and k are constants

Answer 2

Here is some psuedo code for a simple flood fill algorithm:

>>> def flood(i, j, matrix):
...     if 0 <= i < len(matrix) and 0 <= j < len(matrix):
...         if matrix[i][j] == 1:
...             matrix[i][j] = 0
...             for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
...                 flood(i + dx, j + dy, matrix)

>>> count = 0
>>> while True:
...     i, j = get_one(matrix)
...     if i and j: #found a one
...         count += 1
...         flood(i, j, matrix)

Answer 3

This is just the same like finding strongly connected components in a graph, but with the whole thing extended to 3 dimensions. So you can use any of the linear time algorithms for 2D graphs and adapt the DFS also for the 3rd dimension. This should be straight forward.

As those algorithms are linear time you can't get better in terms of running time complexity.