Return to Revisions

I have to agree with both the suggestions by Yves Daoust and Ashish gupta. The following observations should hold:

• A $1 \times S$ block can only be a subset of a $T \times 1$ block if $ S = 1 $.
• An $S \times 1$ block can only be a subset of a $1 \times T$ block if $ S = 1 $.
• Only isolated $ 1 \times 1 $ blocks (without white neighbors) are not subsets of a larger blocks.
• $ 1 \times T $ blocks in different rows can never be subsets of one another.
• $ T \times 1 $ blocks in different columns can never be subsets of one another.

This should allow You to split the block finding as follows:

1. Find $ 1 \times T $ for $ T > 1 $ in each row separately
2. Find $ T \times 1 $ for $ T > 1 $ in each column separately
3. Find all isolated $ 1 \times 1 $ blocks

Both 1. and 2. can both be reduced to the same 1D problem. The following Python code finds all white segments longer than 1 in a 1D array:

import numpy as np


def find_segments( array_1d ):
  array_1d = np.asarray(array_1d, dtype=bool)
  assert array_1d.ndim == 1

  # append black block for simplicity
  # (otherwise last segment needs separate handling)
  array_1d = np.append(array_1d, 1)

  start = None

  for i,ai in enumerate(array_1d):
    if start is None and ai == 0:
      # segment start found
      start = i

    if start is not None and ai == 1:
      # segment end found
      end = i-1
      if start < end: # <- only accept segments greater than 1 
        yield (start,end) 
      start = None

    i += 1

Finding isolated $ 1 \times 1 $ blocks should be as simple as going through each blocks and looking at its neighbors:

def find_1x1_blocks( array_2d ):
  array_2d = np.asarray(array_2d, dtype=bool)
  assert array_2d.ndim == 2

  # pad with black for simplicity
  array_2d = np.pad(array_2d, 1, constant_values=1)

  print(array_2d)

  for (i,j),aij in np.ndenumerate(array_2d):
    if(
      aij == 0
      and array_2d[i-1,j  ] == 1 # <- North 
      and array_2d[i,  j+1] == 1 # <- East
      and array_2d[i+1,j  ] == 1 # <- South
      and array_2d[i,  j-1] == 1 # <- West
    ):
      # subtract padding
      i -= 1
      j -= 1
      yield (i,j)

Using these two subroutines together, we should be able to find all blocks without duplicates:

def find_all_blocks( array_2d ):  
  array_2d = np.asarray(array_2d, dtype=bool)
  assert array_2d.ndim == 2

  (m,n) = array_2d.shape

  # search rows
  for i in range(m):
    for (j,k) in find_segments(array_2d[i,:]):
      yield { 'y': i, 'x': (j,k) }

  for k in range(n):
    for (i,j) in find_segments(array_2d[:,k]):
      yield { 'y': (i,j), 'x': k }

  for (i,j) in find_1x1_blocks(array_2d):
    yield { 'y': i, 'x': j }

All that's left now is to count the blocks. Let's use Your example:

input = np.array(
  [[1,0,0],
   [0,1,0],
   [0,0,1],
   [0,0,0],
   [1,0,0]]
)

blocks = [*find_all_blocks(input)]

for block in blocks:
  print(block)
# Output:
# {'y': 0, 'x': (1, 2)}
# {'y': 2, 'x': (0, 1)}
# {'y': 3, 'x': (0, 2)}
# {'y': 4, 'x': (1, 2)}
# {'y': (1, 3), 'x': 0}
# {'y': (2, 4), 'x': 1}
# {'y': (0, 1), 'x': 2}
# {'y': (3, 4), 'x': 2}

print(len(blocks))
# Output: 8
```