AutoAndroidController/py/venv/Lib/site-packages/skimage/morphology/_flood_fill.py

"""flood_fill.py - in place flood fill algorithm

This module provides a function to fill all equal (or within tolerance) values
connected to a given seed point with a different value.
"""

import numpy as np

from ..util import crop
from ._flood_fill_cy import _flood_fill_equal, _flood_fill_tolerance
from ._util import (
    _offsets_to_raveled_neighbors,
    _resolve_neighborhood,
    _set_border_values,
)
from .._shared.dtype import numeric_dtype_min_max


def flood_fill(
    image,
    seed_point,
    new_value,
    *,
    footprint=None,
    connectivity=None,
    tolerance=None,
    in_place=False,
):
    """Perform flood filling on an image.

    Starting at a specific `seed_point`, connected points equal or within
    `tolerance` of the seed value are found, then set to `new_value`.

    Parameters
    ----------
    image : ndarray
        An n-dimensional array.
    seed_point : tuple or int
        The point in `image` used as the starting point for the flood fill.  If
        the image is 1D, this point may be given as an integer.
    new_value : `image` type
        New value to set the entire fill.  This must be chosen in agreement
        with the dtype of `image`.
    footprint : ndarray, optional
        The footprint (structuring element) used to determine the neighborhood
        of each evaluated pixel. It must contain only 1's and 0's, have the
        same number of dimensions as `image`. If not given, all adjacent pixels
        are considered as part of the neighborhood (fully connected).
    connectivity : int, optional
        A number used to determine the neighborhood of each evaluated pixel.
        Adjacent pixels whose squared distance from the center is less than or
        equal to `connectivity` are considered neighbors. Ignored if
        `footprint` is not None.
    tolerance : float or int, optional
        If None (default), adjacent values must be strictly equal to the
        value of `image` at `seed_point` to be filled.  This is fastest.
        If a tolerance is provided, adjacent points with values within plus or
        minus tolerance from the seed point are filled (inclusive).
    in_place : bool, optional
        If True, flood filling is applied to `image` in place.  If False, the
        flood filled result is returned without modifying the input `image`
        (default).

    Returns
    -------
    filled : ndarray
        An array with the same shape as `image` is returned, with values in
        areas connected to and equal (or within tolerance of) the seed point
        replaced with `new_value`.

    Notes
    -----
    The conceptual analogy of this operation is the 'paint bucket' tool in many
    raster graphics programs.

    Examples
    --------
    >>> from skimage.morphology import flood_fill
    >>> image = np.zeros((4, 7), dtype=int)
    >>> image[1:3, 1:3] = 1
    >>> image[3, 0] = 1
    >>> image[1:3, 4:6] = 2
    >>> image[3, 6] = 3
    >>> image
    array([[0, 0, 0, 0, 0, 0, 0],
           [0, 1, 1, 0, 2, 2, 0],
           [0, 1, 1, 0, 2, 2, 0],
           [1, 0, 0, 0, 0, 0, 3]])

    Fill connected ones with 5, with full connectivity (diagonals included):

    >>> flood_fill(image, (1, 1), 5)
    array([[0, 0, 0, 0, 0, 0, 0],
           [0, 5, 5, 0, 2, 2, 0],
           [0, 5, 5, 0, 2, 2, 0],
           [5, 0, 0, 0, 0, 0, 3]])

    Fill connected ones with 5, excluding diagonal points (connectivity 1):

    >>> flood_fill(image, (1, 1), 5, connectivity=1)
    array([[0, 0, 0, 0, 0, 0, 0],
           [0, 5, 5, 0, 2, 2, 0],
           [0, 5, 5, 0, 2, 2, 0],
           [1, 0, 0, 0, 0, 0, 3]])

    Fill with a tolerance:

    >>> flood_fill(image, (0, 0), 5, tolerance=1)
    array([[5, 5, 5, 5, 5, 5, 5],
           [5, 5, 5, 5, 2, 2, 5],
           [5, 5, 5, 5, 2, 2, 5],
           [5, 5, 5, 5, 5, 5, 3]])
    """
    mask = flood(
        image,
        seed_point,
        footprint=footprint,
        connectivity=connectivity,
        tolerance=tolerance,
    )

    if not in_place:
        image = image.copy()

    image[mask] = new_value
    return image


def flood(image, seed_point, *, footprint=None, connectivity=None, tolerance=None):
    """Mask corresponding to a flood fill.

    Starting at a specific `seed_point`, connected points equal or within
    `tolerance` of the seed value are found.

    Parameters
    ----------
    image : ndarray
        An n-dimensional array.
    seed_point : tuple or int
        The point in `image` used as the starting point for the flood fill.  If
        the image is 1D, this point may be given as an integer.
    footprint : ndarray, optional
        The footprint (structuring element) used to determine the neighborhood
        of each evaluated pixel. It must contain only 1's and 0's, have the
        same number of dimensions as `image`. If not given, all adjacent pixels
        are considered as part of the neighborhood (fully connected).
    connectivity : int, optional
        A number used to determine the neighborhood of each evaluated pixel.
        Adjacent pixels whose squared distance from the center is less than or
        equal to `connectivity` are considered neighbors. Ignored if
        `footprint` is not None.
    tolerance : float or int, optional
        If None (default), adjacent values must be strictly equal to the
        initial value of `image` at `seed_point`.  This is fastest.  If a value
        is given, a comparison will be done at every point and if within
        tolerance of the initial value will also be filled (inclusive).

    Returns
    -------
    mask : ndarray
        A Boolean array with the same shape as `image` is returned, with True
        values for areas connected to and equal (or within tolerance of) the
        seed point.  All other values are False.

    Notes
    -----
    The conceptual analogy of this operation is the 'paint bucket' tool in many
    raster graphics programs.  This function returns just the mask
    representing the fill.

    If indices are desired rather than masks for memory reasons, the user can
    simply run `numpy.nonzero` on the result, save the indices, and discard
    this mask.

    Examples
    --------
    >>> from skimage.morphology import flood
    >>> image = np.zeros((4, 7), dtype=int)
    >>> image[1:3, 1:3] = 1
    >>> image[3, 0] = 1
    >>> image[1:3, 4:6] = 2
    >>> image[3, 6] = 3
    >>> image
    array([[0, 0, 0, 0, 0, 0, 0],
           [0, 1, 1, 0, 2, 2, 0],
           [0, 1, 1, 0, 2, 2, 0],
           [1, 0, 0, 0, 0, 0, 3]])

    Fill connected ones with 5, with full connectivity (diagonals included):

    >>> mask = flood(image, (1, 1))
    >>> image_flooded = image.copy()
    >>> image_flooded[mask] = 5
    >>> image_flooded
    array([[0, 0, 0, 0, 0, 0, 0],
           [0, 5, 5, 0, 2, 2, 0],
           [0, 5, 5, 0, 2, 2, 0],
           [5, 0, 0, 0, 0, 0, 3]])

    Fill connected ones with 5, excluding diagonal points (connectivity 1):

    >>> mask = flood(image, (1, 1), connectivity=1)
    >>> image_flooded = image.copy()
    >>> image_flooded[mask] = 5
    >>> image_flooded
    array([[0, 0, 0, 0, 0, 0, 0],
           [0, 5, 5, 0, 2, 2, 0],
           [0, 5, 5, 0, 2, 2, 0],
           [1, 0, 0, 0, 0, 0, 3]])

    Fill with a tolerance:

    >>> mask = flood(image, (0, 0), tolerance=1)
    >>> image_flooded = image.copy()
    >>> image_flooded[mask] = 5
    >>> image_flooded
    array([[5, 5, 5, 5, 5, 5, 5],
           [5, 5, 5, 5, 2, 2, 5],
           [5, 5, 5, 5, 2, 2, 5],
           [5, 5, 5, 5, 5, 5, 3]])
    """
    # Correct start point in ravelled image - only copy if non-contiguous
    image = np.asarray(image)
    if image.flags.f_contiguous is True:
        order = 'F'
    elif image.flags.c_contiguous is True:
        order = 'C'
    else:
        image = np.ascontiguousarray(image)
        order = 'C'

    # Shortcut for rank zero
    if 0 in image.shape:
        return np.zeros(image.shape, dtype=bool)

    # Convenience for 1d input
    try:
        iter(seed_point)
    except TypeError:
        seed_point = (seed_point,)

    seed_value = image[seed_point]
    seed_point = tuple(np.asarray(seed_point) % image.shape)

    footprint = _resolve_neighborhood(
        footprint, connectivity, image.ndim, enforce_adjacency=False
    )
    center = tuple(s // 2 for s in footprint.shape)
    # Compute padding width as the maximum offset to neighbors on each axis.
    # Generates a 2-tuple of (pad_start, pad_end) for each axis.
    pad_width = [
        (np.max(np.abs(idx - c)),) * 2 for idx, c in zip(np.nonzero(footprint), center)
    ]

    # Must annotate borders
    working_image = np.pad(
        image, pad_width, mode='constant', constant_values=image.min()
    )
    # Stride-aware neighbors - works for both C- and Fortran-contiguity
    ravelled_seed_idx = np.ravel_multi_index(
        [i + pad_start for i, (pad_start, pad_end) in zip(seed_point, pad_width)],
        working_image.shape,
        order=order,
    )
    neighbor_offsets = _offsets_to_raveled_neighbors(
        working_image.shape, footprint, center=center, order=order
    )

    # Use a set of flags; see _flood_fill_cy.pyx for meanings
    flags = np.zeros(working_image.shape, dtype=np.uint8, order=order)
    _set_border_values(flags, value=2, border_width=pad_width)

    try:
        if tolerance is not None:
            tolerance = abs(tolerance)
            # Account for over- & underflow problems with seed_value ± tolerance
            # in a way that works with NumPy 1 & 2
            min_value, max_value = numeric_dtype_min_max(seed_value.dtype)
            low_tol = max(min_value.item(), seed_value.item() - tolerance)
            high_tol = min(max_value.item(), seed_value.item() + tolerance)

            _flood_fill_tolerance(
                working_image.ravel(order),
                flags.ravel(order),
                neighbor_offsets,
                ravelled_seed_idx,
                seed_value,
                low_tol,
                high_tol,
            )
        else:
            _flood_fill_equal(
                working_image.ravel(order),
                flags.ravel(order),
                neighbor_offsets,
                ravelled_seed_idx,
                seed_value,
            )
    except TypeError:
        if working_image.dtype == np.float16:
            # Provide the user with clearer error message
            raise TypeError(
                "dtype of `image` is float16 which is not "
                "supported, try upcasting to float32"
            )
        else:
            raise

    # Output what the user requested; view does not create a new copy.
    return crop(flags, pad_width, copy=False).view(bool)