floodFill function

List<Point<int>> floodFill(Artifact binaryPixels, Artifact visited, int startX, int startY,)

Performs a highly optimized flood fill algorithm on a binary image matrix.

This implementation uses direct array access and efficient data structures to significantly improve performance over the traditional approach.

Parameters: binaryPixels: A Matrix representing the binary image where true values indicate filled pixels. visited: A Matrix of the same size as binaryPixels to keep track of visited pixels. startX: The starting X coordinate for the flood fill. startY: The starting Y coordinate for the flood fill.

Returns: A List of Point objects representing all connected points found during the flood fill process.

Implementation

List<Point<int>> floodFill(
  final Artifact binaryPixels,
  final Artifact visited,
  final int startX,
  final int startY,
) {
  final int width = binaryPixels.cols;
  final int height = binaryPixels.rows;

  // Early bounds check
  if (startX < 0 || startX >= width || startY < 0 || startY >= height) {
    return const [];
  }

  // Early check for valid starting pixel
  if (!binaryPixels.cellGet(startX, startY)) {
    return const [];
  }

  // Direct access to the underlying arrays
  final Uint8List pixelData = binaryPixels.matrix;
  final Uint8List visitedData = visited.matrix;

  // Pre-allocate with estimated capacity to reduce reallocations
  final List<Point<int>> connectedPoints = <Point<int>>[];
  final Queue<int> queue = Queue<int>();

  // Calculate initial index
  final int startIndex = startY * width + startX;

  // Mark start point as visited and add to queue
  visitedData[startIndex] = 1;
  queue.add(startIndex);
  connectedPoints.add(Point(startX, startY));

  // Direction offsets for adjacent pixels (including diagonals)
  const List<int> rowOffsets = [-1, -1, -1, 0, 0, 1, 1, 1]; // Row adjustments
  const List<int> colOffsets = [
    -1,
    0,
    1,
    -1,
    1,
    -1,
    0,
    1,
  ]; // Column adjustments

  while (queue.isNotEmpty) {
    final int currentIndex = queue.removeFirst();
    final int x = currentIndex % width;
    final int y = currentIndex ~/ width;

    // Check all eight directions (including diagonals)
    for (int i = 0; i < 8; i++) {
      final int nx = x + colOffsets[i];
      final int ny = y + rowOffsets[i];

      // Skip out-of-bounds
      if (nx < 0 || nx >= width || ny < 0 || ny >= height) {
        continue;
      }

      final int neighborIndex = ny * width + nx;

      // Check if neighbor is valid and not visited
      if (pixelData[neighborIndex] == 1 && visitedData[neighborIndex] == 0) {
        visitedData[neighborIndex] = 1;
        queue.add(neighborIndex);
        connectedPoints.add(Point(nx, ny));
      }
    }
  }

  return connectedPoints;
}