Flood fill - Cython

flood_fill.pyx

import numpy as np
cimport numpy as cnp


# Compiler directives
@cython.cdivision(True)
@cython.boundscheck(False)
@cython.nonecheck(False)
@cython.wraparound(False)
def flood_fill(unsigned char[:, ::1] data, tuple start_coords,
               Py_ssize_t fill_value):
    """
    Flood fill algorithm
    
    Parameters
    ----------
    data : (M, N) ndarray of uint8 type
        Image with flood to be filled. Modified inplace.
    start_coords : tuple
        Length-2 tuple of ints defining (row, col) start coordinates.
    fill_value : int
        Value the flooded area will take after the fill.
        
    Returns
    -------
    None, ``data`` is modified inplace.
    """
    cdef:
        Py_ssize_t x, y, xsize, ysize, orig_value
        set stack
    
    xsize = data.shape[0]
    ysize = data.shape[1]
    orig_value = data[start_coords[0], start_coords[1]]
    
    if fill_value == orig_value:
        raise ValueError("Filling region with same value "
                         "already present is unsupported. "
                         "Did you already fill this region?")
    
    stack = set(((start_coords[0], start_coords[1]),))

    while stack:
        x, y = stack.pop()

        if data[x, y] == orig_value:
            data[x, y] = fill_value
            if x > 0:
                stack.add((x - 1, y))
            if x < (xsize - 1):
                stack.add((x + 1, y))
            if y > 0:
                stack.add((x, y - 1))
            if y < (ysize - 1):
                stack.add((x, y + 1))