cluster.py

import numpy as np

# Some array of booleans of width w and height h
#occupied_map = np.array([[0,0,0,0],
#                         [1,1,1,0],
#                         [0,0,0,1],
#                         [0,1,0,1],
#                         [0,1,0,0],
#                         [0,1,1,0],
#                         [0,0,0,0]], dtype=np.int32).astype(np.bool)

occupied_map = np.array([[0,0,0,0,1,1,1],
                         [0,0,0,0,1,0,1],
                         [0,1,0,1,0,0,0],
                         [1,1,0,0,0,0,0]], dtype=np.int32).astype(np.bool)

w = occupied_map.shape[1]
h = occupied_map.shape[0]

# Some array of unique integer ids of width w and height h
id_map       = np.reshape(np.arange(h*w, dtype=np.int32), [h,w])

# Negative one means the cell has not been visited yet
cluster_map = -np.ones([h,w], dtype=np.int32)

# Number each cluster found starting at 0
current_cluster = 0

# Loop over all cells
for y in range(0,h):
    for x in range(0,w):

        # If cell (y,x) is still unvisited and is occupied, then start a flood fill at this location
        if (cluster_map[y,x] == -1 and occupied_map[y,x]):

            # List will hold all the ids within this cluster
            cluster_ids = []

            # Visit all cells in queue until
            cell_queue = [(y,x)]
            while (len(cell_queue) > 0):

                # Pop the last cell off the queue and process it
                cy,cx = cell_queue[-1]
                cell_queue = cell_queue[0:-1]  

                # If cell (cy,cx) is still unvisited, then start a flood fill at this location
                # We know (cy,cx) must be occupied, because it was added to the queue in the first place
                if (cluster_map[cy,cx] == -1):

                    # Claim (cy,cx) for the current cluster
                    cluster_map[cy,cx] = current_cluster

                    # Add the cell id to the cluster list
                    cluster_ids.append(id_map[cy,cx])

                    # Up, Down, Left, Right, (No Diagonals)
                    neighbours = [(-1,0), (1,0), (0,-1), (0,1)]
                    
                    # Visit neighbours of (cy,cx)
                    for (dy,dx) in neighbours:
                        if (((cy+dy) < 0 or (cy+dy) >= h) or
                            ((cx+dx) < 0 or (cx+dx) >= w)): continue
                        
                        # If neighbour cell is occupied, then add it to the queue of cells to visit
                        if (occupied_map[cy+dy, cx+dx]): 
                            cell_queue.append((cy+dy, cx+dx))
                            

            # Print ids in this cluster
            print('Cluster', current_cluster, 'contains ids', sorted(cluster_ids))

            # The full cluster has been found, increment the current cluster
            current_cluster += 1