Привет всем. Как ранее я рассказывал в своих статьях, мне нравится заниматься приложениями для сферы развлечений. И недавно появилась задача - реализовать фичу с раскраской картинок.
Сегодня мы рассмотрим, как реализовать такую раскраску для растровых изображений с помощью алгоритма flood fill. Посмотрим, что уже есть на pub.dev, заглянем немного в теорию этого алгоритма, реализуем его на dart с помощью ChatGPT и применим во flutter приложении.
Ресерч в pub.dev
На pub.dev уже есть библиотека floodfill_image, которая предоставляет возможности закрашивания png и jpg картинок.
Доступные фичи:
1) Загрузка картинки с интернета и с ассетов
2) Выбор цвета закрашивания
3) Выбор цветов, которые не будут перекрашиваться
4) Можно указать чувствительность, то есть какие соседние цвета тоже должны закрашиваться, если они немного отличаются по оттенку
5) Дополнительно: коллбеки, которые можно использовать для сохранения прогресса раскрашивания, и виджет плейсхолдер для загрузки
Плюсы:
1) Поддерживается всеми платформами
2) Удобно использовать
Недостатки текущей реализации:
1) Первое, на что я обратил внимание, - это невозможность задать более высокую чувствительность. Из-за маленькой чувствительности рядом с контурами возникают белые незакрашенные области (видно на гифке)
2) Качество картинки сильно теряется, и на это никак не повлиять без изменения в самой библиотеке
3) Библиотека уже более 2 лет не обновлялась. На момент написания статьи версия библиотеки 0.0.8
Это с одной стороны хорошо: если до сих пор нет конфликтов с новыми версиями фреймворка и библиотека вполне выполняет свои задачи, то она была написана хорошо.
Но с другой стороны - все-таки код имеет свойство устаревать. Те правила и стиль, которые были актуальны тогда, сейчас делают его все менее понятным.
В связи с этим поднимается вопрос - поправить имеющуюся в библиотеке реализацию, копаясь в чужом коде, либо писать свои костыли.
И я сначала выбрал первый вариант. Не буду вдаваться в подробности, как сделать форк и подтягивать библиотеку по url, так как это материал для других статей. Скажу только, что столкнулся с типичными проблемами: линтер ругается, руки чешутся отрефакторить все, что видишь.
В конце концов, малыми потерями я достиг первых двух поставленных целей: поправить чувствительность и повысить качество.
И на этом можно остановиться, так как задача в целом решена.
А теперь давайте представим, что нет готовой реализации алгоритма на flutter, но есть Гугл, Википедия и ChatGPT
Что за алгоритм flood fill?
Чтобы ответить на этот вопрос, я поступил как во времена вуза - погуглил и нашел ответ в Википедии. Там написано:
Flood fill, also called seed fill, is a flooding algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. A variant called boundary fill uses the same algorithms but is defined as the area connected to a given node that does not have a particular attribute.
Тут как бы ничего необычного. Просто дали название для алгоритма, который используется при изменении области значений в многомерном массиве.
В той же Википедии приведены 4 примера реализации алгоритма:
Stack-based recursive implementation (four-way)
Span filling
Graph-theoretic filling
Walk-based filling (Fixed-memory method)
В классическом варианте для выполнения алгоритма нам требуются двухмерный массив, координата, текущее значение в указанной координате и новое значение, которым будет заменяться также соседние значения, если они равны значению в текущей координате.
Прежде чем приступить к реализации алгоритма, напишем, какой должен быть общий интерфейс для всех реализаций:
abstract class FloodFill {
final List<List<int>> image;
const FloodFill(this.image);
void fill(int startX, int startY, int newColor);
}Stack-based recursive implementation
Самый простой в плане понимания и реализации, на мой взгляд, первый вариант, где используется рекурсия. Логика простая - проверяем пиксель, а потом соседние, и так далее, пока не пройдем по всем пикселям, которые удовлетворяют определенным условиям. Вот так выглядит алгоритм, если использовать рекурсию напрямую.
Я попросил ChatGPT написать реализацию рекурсивного алгоритма flood fill на Dart.
Промпт
Write me an implementation of this algorithm for dart language:
Flood-fill (node):
If node is not Inside return.
Set the node
Perform Flood-fill one step to the south of node.
Perform Flood-fill one step to the north of node
Perform Flood-fill one step to the west of node
Perform Flood-fill one step to the east of node
Return.use such interface:
abstract class FloodFill {
final List<List<int>> image;
const FloodFill(this.image);
void fill(int startX, int startY, int newColor);
}
class BasicFloodFill extends FloodFill {
const BasicFloodFill(List<List<int>> image) : super(image);
@override
void fill(int startX, int startY, int newColor) {
int originalColor = image[startX][startY];
_floodFillUtil(startX, startY, originalColor, newColor);
}
void _floodFillUtil(int x, int y, int originalColor, int newColor) {
// Check if current node is inside the boundary and not already filled
if (!_isInside(x, y) || image[x][y] != originalColor) return;
// Set the node
image[x][y] = newColor;
// Perform flood-fill one step in each direction
_floodFillUtil(x + 1, y, originalColor, newColor); // South
_floodFillUtil(x - 1, y, originalColor, newColor); // North
_floodFillUtil(x, y - 1, originalColor, newColor); // West
_floodFillUtil(x, y + 1, originalColor, newColor); // East
}
bool _isInside(int x, int y) {
return x >= 0 && x < image.length && y >= 0 && y < image[0].length;
}
}Тот же рекурсивный алгоритм, но уже с использованием структур данных:
Промпт
Write me an implementation of this algorithm for dart language:
Flood-fill (node):
Set Q to the empty queue or stack.
Add node to the end of Q.
While Q is not empty:
Set n equal to the first element of Q.
Remove first element from Q.
If n is Inside:
Set the n
Add the node to the west of n to the end of Q.
Add the node to the east of n to the end of Q.
Add the node to the north of n to the end of Q.
Add the node to the south of n to the end of Q.
Continue looping until Q is exhausted.
Return.
Use such interface:
abstract class FloodFill {
final List<List<int>> image;
const FloodFill(this.image);
void fill(int startX, int startY, int newColor);
}
import 'dart:collection';
class Point {
final int x;
final int y;
const Point(this.x, this.y);
}
class FloodFillQueueImpl extends FloodFill {
const FloodFillQueueImpl(List<List<int>> image) : super(image);
@override
void fill(int startX, int startY, int newColor) {
final int oldColor = image[startX][startY];
final Queue<Point> queue = Queue();
queue.add(Point(startY, startX));
while (queue.isNotEmpty) {
final Point point = queue.removeFirst();
final int x = point.x;
final int y = point.y;
if (image[y][x] == oldColor) {
image[y][x] = newColor;
if (x > 0) {
queue.add(Point(x - 1, y));
}
if (x < image[y].length - 1) {
queue.add(Point(x + 1, y));
}
if (y > 0) {
queue.add(Point(x, y - 1));
}
if (y < image.length - 1) {
queue.add(Point(x, y + 1));
}
}
}
}
}Span filling
Этот алгоритм работает путем последовательного рассмотрения горизонтальных линий изображения и заполнения участков между пересечениями этих линий с краями области.
Промпт
Write me an implementation of this algorithm for dart language:
fn fill(x, y):
if not Inside(x, y) then return
let s = new empty queue or stack
Add (x, x, y, 1) to s
Add (x, x, y - 1, -1) to s
while s is not empty:
Remove an (x1, x2, y, dy) from s
let x = x1
if Inside(x, y):
while Inside(x - 1, y):
Set(x - 1, y)
x = x - 1
if x < x1:
Add (x, x1 - 1, y - dy, -dy) to s
while x1 <= x2:
while Inside(x1, y):
Set(x1, y)
x1 = x1 + 1
if x1 > x:
Add (x, x1 - 1, y + dy, dy) to s
if x1 - 1 > x2:
Add (x2 + 1, x1 - 1, y - dy, -dy) to s
x1 = x1 + 1
while x1 < x2 and not Inside(x1, y):
x1 = x1 + 1
x = x1
Use such interface:
abstract class abstract class FloodFill {
final List<List<int>> image;
const FloodFill(this.image);
void fill(int startX, int startY, int newColor);
}
class FloodFillSpanImpl extends FloodFill {
const FloodFillSpanImpl(List<List<int>> image) : super(image);
// Check if the point is inside the canvas and matches the target color
bool _isInside(int x, int y, int targetColor) {
return x >= 0 && y >= 0 && x < image.length && y < image[0].length && image[x][y] == targetColor;
}
// Set a point to the replacement color
void _setColor(int x, int y, int replacementColor) {
image[x][y] = replacementColor;
}
@override
void fill(int startX, int startY, int newColor) {
final targetColor = image[startX][startY];
if (!_isInside(startX, startY, targetColor)) return;
var s = <List<int>>[];
s.add([startX, startX, startY, 1]);
s.add([startX, startX, startY - 1, -1]);
while (s.isNotEmpty) {
var tuple = s.removeLast();
var x1 = tuple[0];
var x2 = tuple[1];
var y = tuple[2];
var dy = tuple[3];
var nx = x1;
if (_isInside(nx, y, targetColor)) {
while (_isInside(nx - 1, y, targetColor)) {
_setColor(nx - 1, y, newColor);
nx--;
}
if (nx < x1) {
s.add([nx, x1 - 1, y - dy, -dy]);
}
}
while (x1 <= x2) {
while (_isInside(x1, y, targetColor)) {
_setColor(x1, y, newColor);
x1++;
}
if (x1 > nx) {
s.add([nx, x1 - 1, y + dy, dy]);
}
if (x1 - 1 > x2) {
s.add([x2 + 1, x1 - 1, y - dy, -dy]);
}
x1++;
while (x1 < x2 && !_isInside(x1, y, targetColor)) {
x1++;
}
nx = x1;
}
}
}
}Остальные реализации рассматривать не будем, потому что в Graph-theoretic filling нет словами расписанной реализации, как у предыдущих вариантов, и мне не очень хотелось бы разбираться в деталях. А в недостатках алгоритма Walk-based filling написано, что может потратиться много времени в циклах, прежде чем завершиться.
Поскольку есть общий для всех интерфейс, то можно провести небольшие тесты. Будем сравнивать результат и, на всякий случай, скорость выполнения:
Код теста
import 'package:flutter_test/flutter_test.dart';
import 'package:painter/features/examples/algorithms.dart';
void main() {
group(
'FloodFill classic',
() {
test('grid 30x30', () {
final Stopwatch stopwatch = Stopwatch()..start();
List<List<int>> image = [
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3, 3, 3, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
];
BasicFloodFill(image).fill(7, 8, 2);
stopwatch.stop();
print('Elapsed time: ${stopwatch.elapsed}');
List<List<int>> result = [
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 0, 3, 3, 3, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
];
expect(image, result);
});
},
);
group(
'FloodFill queued',
() {
test('grid 30x30', () {
final Stopwatch stopwatch = Stopwatch()..start();
List<List<int>> image = [
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3, 3, 3, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
];
FloodFillQueueImpl(image).fill(7, 8, 2);
stopwatch.stop();
print('Elapsed time: ${stopwatch.elapsed}');
List<List<int>> result = [
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 0, 3, 3, 3, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
];
expect(image, result);
});
},
);
group(
'FloodFill span',
() {
test('grid 30x30', () {
final Stopwatch stopwatch = Stopwatch()..start();
List<List<int>> image = [
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3, 3, 3, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
];
final floodFill = FloodFillSpanImpl(image);
floodFill.fill(7, 8, 2);
stopwatch.stop();
print('Elapsed time: ${stopwatch.elapsed}');
List<List<int>> result = [
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 0, 3, 3, 3, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
];
expect(image, result);
});
},
);
}
Редактируемое изображение из цифр
Результаты запусков нескольких тестов +- следующие:
00:01 +0: FloodFill classic grid 30x30
Elapsed time: 0:00:00.000300
00:01 +1: FloodFill queued grid 30x30
Elapsed time: 0:00:00.000864
00:01 +2: FloodFill span grid 30x30
Elapsed time: 0:00:00.000338
00:01 +3: All tests passed! Отсюда следует вывод, что либо ChatGPT криво реализовал алгоритмы, либо вторая реализация (рекурсия с очередями) действительно сильно медленнее, а лидер - обычная рекурсия.
Реализация в контексте flutter приложения
Интерфейс
Для начала разберемся, какой интерфейс мы хотим иметь для раскраски реальных изображений. Воспользуемся предыдущим вариантом, добавив дженерики:
abstract class FloodFill<T, S> {
final T image;
const FloodFill(this.image);
void fill(int startX, int startY, S newColor);
}Хелперы
Так как мы будем пользоваться стандартной библиотекой dart:ui, то нужно добавить несколько методов-хелперов для работы с ней.
Во-первых, в этой библиотеке нет возможности взаимодействовать с отдельными пикселями изображения напрямую. Поэтому нам необходимы преобразования в такую структуру данных, чтобы эта возможность появилась. Для этих целей подходят байты. Реализуем преобразования в обе стороны:
import 'dart:async';
import 'dart:typed_data';
import 'dart:ui' as ui;
Future<ByteData?> imageToBytes(ui.Image image) async {
final bytes = await image.toByteData(format: ui.ImageByteFormat.rawRgba);
return bytes;
}
Future<ui.Image> imageFromBytes(ByteData bytes, int imageWidth, int imageHeight) {
final Completer<ui.Image> completer = Completer();
ui.decodeImageFromPixels(
bytes.buffer.asUint8List(),
imageWidth,
imageHeight,
ui.PixelFormat.rgba8888,
(img) {
completer.complete(img);
},
);
return completer.future;
}Во-вторых, цвет напрямую мы тоже не можем задавать в байтах, поэтому для него тоже нужны преобразования в байты и обратно.
Цветной пиксель может быть представлен в виде комбинации красного R, зеленого G и синего B цветов разных оттенков. К этой смеси часто также добавляется 4 показатель альфа A, или прозрачность.
Заметки от кэпа
Разные оттенки цвета можно закодировать с помощью комбинаций из 0 и 1 (один бит). Принято кодировать их с помощью 8 битов (2^8 = 256 различных вариантов), или одного байта. Таким образом, один цвет, если он является комбинацией RGBA, может быть представлен как последовательность 8x4=32 нулей или единичек, или 32 битов, или 4 байтов.
Соответственно, в массиве байтов из картинки каждый пиксель идет друг за другом через 4.
В коде выше изображение преобразуется в байты, где цвета представлены в формате RGBA, а Color в библиотеке dart:ui по умолчанию хранит значение в формате ARGB. Это нужно обязательно учитывать:
void setPixelColor({
required int x,
required int y,
required ByteData bytes,
// for correct representation of color bytes' coordinates
// in an array of image bytes
required int imageWidth,
required ui.Color newColor,
}) {
bytes.setUint32(
(x + y * imageWidth) * 4, // offset
colorToIntRGBA(newColor), // value
);
}
ui.Color getPixelColor({
required ByteData bytes,
required int x,
required int y,
required int imageWidth,
}) {
final uint32 = bytes.getUint32((x + y * imageWidth) * 4);
return colorFromIntRGBA(uint32);
}
int colorToIntRGBA(ui.Color color) {
// Extract ARGB components
int a = (color.value >> 24) & 0xFF;
int r = (color.value >> 16) & 0xFF;
int g = (color.value >> 8) & 0xFF;
int b = color.value & 0xFF;
// Convert to RGBA and combine into a single integer
return (r << 24) | (g << 16) | (b << 8) | a;
}
ui.Color colorFromIntRGBA(int uint32Rgba) {
// Extract RGBA components
int r = (uint32Rgba >> 24) & 0xFF;
int g = (uint32Rgba >> 16) & 0xFF;
int b = (uint32Rgba >> 8) & 0xFF;
int a = uint32Rgba & 0xFF;
// Convert to ARGB format and create a Color object
return ui.Color.fromARGB(a, r, g, b);
}В-третьих, хелпер, который позволяет сравнивать почти похожие цвета, то есть по сути тут можно передавать чувствительность, как в рассмотренной в начале библиотеке. Я задал по умолчанию значение threshold = 50:
bool isAlmostSameColor({
required ui.Color pixelColor,
required ui.Color checkColor,
required int imageWidth,
}) {
const int threshold = 50;
final int rDiff = (pixelColor.red - checkColor.red).abs();
final int gDiff = (pixelColor.green - checkColor.green).abs();
final int bDiff = (pixelColor.blue - checkColor.blue).abs();
return rDiff < threshold && gDiff < threshold && bDiff < threshold;
}Реализация алгоритма
Поскольку есть асинхронные преобразования, то метод, который был в ранее в классе FloodFill уже не совсем подходит, поэтому сделаем еще один апгрейд:
abstract class FloodFill<T, S> {
final T image;
const FloodFill(this.image);
FutureOr<T?> fill(int startX, int startY, S newColor);
}В этом варианте метод fill() в зависимости от реализации может возвращать результат T? image или асинхронно, или синхронно.
Скорректированные имплементации алгоримтов
class BasicFloodFill extends FloodFill<List<List<int>>, int> {
const BasicFloodFill(List<List<int>> image) : super(image);
@override
List<List<int>>? fill(int startX, int startY, int newColor) {
int originalColor = image[startX][startY];
_floodFillUtil(startX, startY, originalColor, newColor);
return image;
}
void _floodFillUtil(int x, int y, int originalColor, int newColor) {
// Check if current node is inside the boundary and not already filled
if (!_isInside(x, y) || image[x][y] != originalColor) return;
// Set the node
image[x][y] = newColor;
// Perform flood-fill one step in each direction
_floodFillUtil(x + 1, y, originalColor, newColor); // South
_floodFillUtil(x - 1, y, originalColor, newColor); // North
_floodFillUtil(x, y - 1, originalColor, newColor); // West
_floodFillUtil(x, y + 1, originalColor, newColor); // East
}
bool _isInside(int x, int y) {
return x >= 0 && x < image.length && y >= 0 && y < image[0].length;
}
}
class Point {
final int x;
final int y;
const Point(this.x, this.y);
}
class FloodFillQueueImpl extends FloodFill<List<List<int>>, int> {
const FloodFillQueueImpl(List<List<int>> image) : super(image);
@override
List<List<int>>? fill(int startX, int startY, int newColor) {
final int oldColor = image[startX][startY];
final int width = image[0].length;
final int height = image.length;
final Queue<Point> queue = Queue();
queue.add(Point(startY, startX));
while (queue.isNotEmpty) {
final Point point = queue.removeFirst();
final int x = point.x;
final int y = point.y;
if (image[y][x] == oldColor) {
image[y][x] = newColor;
if (x > 0) {
queue.add(Point(x - 1, y));
}
if (x < width - 1) {
queue.add(Point(x + 1, y));
}
if (y > 0) {
queue.add(Point(x, y - 1));
}
if (y < height - 1) {
queue.add(Point(x, y + 1));
}
}
}
return image;
}
}
class FloodFillSpanImpl extends FloodFill<List<List<int>>, int> {
const FloodFillSpanImpl(List<List<int>> image) : super(image);
// Check if the point is inside the canvas and matches the target color
bool _isInside(int x, int y, int targetColor) {
return x >= 0 && y >= 0 && x < image.length && y < image[0].length && image[x][y] == targetColor;
}
// Set a point to the replacement color
void _setColor(int x, int y, int replacementColor) {
image[x][y] = replacementColor;
}
@override
List<List<int>>? fill(int startX, int startY, int newColor) {
final targetColor = image[startX][startY];
if (!_isInside(startX, startY, targetColor)) return null;
var s = <List<int>>[];
s.add([startX, startX, startY, 1]);
s.add([startX, startX, startY - 1, -1]);
while (s.isNotEmpty) {
var tuple = s.removeLast();
var x1 = tuple[0];
var x2 = tuple[1];
var y = tuple[2];
var dy = tuple[3];
var nx = x1;
if (_isInside(nx, y, targetColor)) {
while (_isInside(nx - 1, y, targetColor)) {
_setColor(nx - 1, y, newColor);
nx--;
}
if (nx < x1) {
s.add([nx, x1 - 1, y - dy, -dy]);
}
}
while (x1 <= x2) {
while (_isInside(x1, y, targetColor)) {
_setColor(x1, y, newColor);
x1++;
}
if (x1 > nx) {
s.add([nx, x1 - 1, y + dy, dy]);
}
if (x1 - 1 > x2) {
s.add([x2 + 1, x1 - 1, y - dy, -dy]);
}
x1++;
while (x1 < x2 && !_isInside(x1, y, targetColor)) {
x1++;
}
nx = x1;
}
}
return image;
}
}
Попросим ChatGPT реализовать алгоритм:
Промпт
I have this interface
abstract class FloodFill<T, S> {
final T image;
const FloodFill(this.image);
FutureOr<T?> fill(int startX, int startY, S newColor);
}I need you to upgrade an implementation below for the new values:
class BasicFloodFill extends FloodFill<List<List<int>>, int> {
const BasicFloodFill(List<List<int>> image) : super(image);@override
List<List<int>>? fill(int startX, int startY, int newColor) {
int originalColor = image[startX][startY];
_floodFillUtil(startX, startY, originalColor, newColor);
return image;
}void _floodFillUtil(int x, int y, int originalColor, int newColor) {
// Check if current node is inside the boundary and not already filled
if (!_isInside(x, y) || image[x][y] != originalColor) return;// Set the node
image[x][y] = newColor;// Perform flood-fill one step in each direction
_floodFillUtil(x + 1, y, originalColor, newColor); // South
_floodFillUtil(x - 1, y, originalColor, newColor); // North
_floodFillUtil(x, y - 1, originalColor, newColor); // West
_floodFillUtil(x, y + 1, originalColor, newColor); // Eastbool _isInside(int x, int y) {
return x >= 0 && x < image.length && y >= 0 && y < image[0].length;
}
}Where T is an ui.Image from the library dart:ui as ui, and S is an ui.Color also from this library.
Please, use these helpers:
Future<ByteData?> imageToBytes(ui.Image image) async {
final bytes = await image.toByteData(format: ui.ImageByteFormat.rawRgba);
return bytes;
}Future<ui.Image> imageFromBytes(ByteData bytes, int imageWidth, int imageHeight) {
final Completer<ui.Image> completer = Completer();
ui.decodeImageFromPixels(
bytes.buffer.asUint8List(),
imageWidth,
imageHeight,
ui.PixelFormat.rgba8888,
(img) {
completer.complete(img);
},
);
return completer.future;
}bool isAlmostSameColor({
required ui.Color pixelColor,
required ui.Color checkColor,
required int imageWidth,
}) {
const int threshold = 50;
final int rDiff = (pixelColor.red - checkColor.red).abs();
final int gDiff = (pixelColor.green - checkColor.green).abs();
final int bDiff = (pixelColor.blue - checkColor.blue).abs();
return rDiff < threshold && gDiff < threshold && bDiff < threshold;
}void setPixelColor({
required int x,
required int y,
required ByteData bytes,
required int imageWidth,
required ui.Color newColor,
}) {
bytes.setUint32(
(x + y * imageWidth) * 4,
colorToIntRGBA(newColor),
);
}ui.Color getPixelColor({
required ByteData bytes,
required int x,
required int y,
required int imageWidth,
}) {
final uint32 = bytes.getUint32((x + y * imageWidth) * 4);
return colorFromIntRGBA(uint32);
}int colorToIntRGBA(ui.Color color) {
// Extract ARGB components
int a = (color.value >> 24) & 0xFF;
int r = (color.value >> 16) & 0xFF;
int g = (color.value >> 8) & 0xFF;
int b = color.value & 0xFF;// Convert to RGBA and combine into a single integer
return (r << 24) | (g << 16) | (b << 8) | a;
}ui.Color colorFromIntRGBA(int uint32Rgba) {
// Extract RGBA components
int r = (uint32Rgba >> 24) & 0xFF;
int g = (uint32Rgba >> 16) & 0xFF;
int b = (uint32Rgba >> 8) & 0xFF;
int a = uint32Rgba & 0xFF;// Convert to ARGB format and create a Color object
return ui.Color.fromARGB(a, r, g, b);
}
import 'dart:async';
import 'dart:typed_data';
import 'dart:ui' as ui;
class ImageFloodFill extends FloodFill<ui.Image, ui.Color> {
ImageFloodFill(ui.Image image) : super(image);
@override
Future<ui.Image?> fill(int startX, int startY, ui.Color newColor) async {
ByteData? byteData = await imageToBytes(image);
if (byteData == null) return null;
int width = image.width;
int height = image.height;
ui.Color originalColor = getPixelColor(bytes: byteData, x: startX, y: startY, imageWidth: width);
_floodFillUtil(byteData, startX, startY, width, height, originalColor, newColor);
return imageFromBytes(byteData, width, height);
}
void _floodFillUtil(ByteData bytes, int x, int y, int width, int height, ui.Color originalColor, ui.Color newColor) {
// Check if current node is inside the boundary and not already filled
if (!_isInside(x, y, width, height) || !isAlmostSameColor(pixelColor: getPixelColor(bytes: bytes, x: x, y: y, imageWidth: width), checkColor: originalColor, imageWidth: width)) return;
// Set the node
setPixelColor(x: x, y: y, bytes: bytes, imageWidth: width, newColor: newColor);
// Perform flood-fill one step in each direction
_floodFillUtil(bytes, x + 1, y, width, height, originalColor, newColor); // East
_floodFillUtil(bytes, x - 1, y, width, height, originalColor, newColor); // West
_floodFillUtil(bytes, x, y - 1, width, height, originalColor, newColor); // North
_floodFillUtil(bytes, x, y + 1, width, height, originalColor, newColor); // South
}
bool _isInside(int x, int y, int width, int height) {
return x >= 0 && x < width && y >= 0 && y < height;
}
}Аналогично для Queued и Span:
Queued
import 'dart:async';
import 'dart:typed_data';
import 'dart:ui' as ui;
import 'dart:collection';
class ImageFloodFillQueueImpl extends FloodFill<ui.Image, ui.Color> {
ImageFloodFillQueueImpl(ui.Image image) : super(image);
@override
Future<ui.Image?> fill(int startX, int startY, ui.Color newColor) async {
ByteData? byteData = await imageToBytes(image);
if (byteData == null) return null;
int width = image.width;
int height = image.height;
ui.Color oldColor = getPixelColor(bytes: byteData, x: startX, y: startY, imageWidth: width);
final Queue<Point> queue = Queue();
queue.add(Point(startX, startY));
while (queue.isNotEmpty) {
final Point point = queue.removeFirst();
final int x = point.x;
final int y = point.y;
if (isAlmostSameColor(pixelColor: getPixelColor(bytes: byteData, x: x, y: y, imageWidth: width), checkColor: oldColor, imageWidth: width)) {
setPixelColor(x: x, y: y, bytes: byteData, imageWidth: width, newColor: newColor);
if (x > 0) queue.add(Point(x - 1, y));
if (x < width - 1) queue.add(Point(x + 1, y));
if (y > 0) queue.add(Point(x, y - 1));
if (y < height - 1) queue.add(Point(x, y + 1));
}
}
return imageFromBytes(byteData, width, height);
}
}
class Point {
final int x;
final int y;
const Point(this.x, this.y);
}Span
import 'dart:async';
import 'dart:typed_data';
import 'dart:ui' as ui;
class ImageFloodFillSpanImpl extends FloodFill<ui.Image, ui.Color> {
ImageFloodFillSpanImpl(ui.Image image) : super(image);
@override
Future<ui.Image?> fill(int startX, int startY, ui.Color newColor) async {
ByteData? byteData = await imageToBytes(image);
if (byteData == null) return null;
int width = image.width;
int height = image.height;
ui.Color targetColor = getPixelColor(bytes: byteData, x: startX, y: startY, imageWidth: width);
var s = <List<int>>[];
s.add([startX, startX, startY, 1]);
s.add([startX, startX, startY - 1, -1]);
while (s.isNotEmpty) {
var tuple = s.removeLast();
var x1 = tuple[0];
var x2 = tuple[1];
var y = tuple[2];
var dy = tuple[3];
var nx = x1;
if (_isInside(nx, y, width, height, byteData, targetColor)) {
while (_isInside(nx - 1, y, width, height, byteData, targetColor)) {
setPixelColor(x: nx - 1, y: y, bytes: byteData, imageWidth: width, newColor: newColor);
nx--;
}
if (nx < x1) {
s.add([nx, x1 - 1, y - dy, -dy]);
}
}
while (x1 <= x2) {
while (_isInside(x1, y, width, height, byteData, targetColor)) {
setPixelColor(x: x1, y: y, bytes: byteData, imageWidth: width, newColor: newColor);
x1++;
}
if (x1 > nx) {
s.add([nx, x1 - 1, y + dy, dy]);
}
if (x1 - 1 > x2) {
s.add([x2 + 1, x1 - 1, y - dy, -dy]);
}
x1++;
while (x1 < x2 && !_isInside(x1, y, width, height, byteData, targetColor)) {
x1++;
}
nx = x1;
}
}
return imageFromBytes(byteData, width, height);
}
bool _isInside(int x, int y, int width, int height, ByteData bytes, ui.Color targetColor) {
if (x < 0 || x >= width || y < 0 || y >= height) return false;
return isAlmostSameColor(pixelColor: getPixelColor(bytes: bytes, x: x, y: y, imageWidth: width), checkColor: targetColor, imageWidth: width);
}
}Проверка результата
Проверим работоспособность алгоритма. Для этого сверстаем экранчик, на котором можно попробовать алгоритм на картинке.
Требования:
Картинка загружается из интернета по url
При нажатии на какую-либо область она закрашивается в красный цвет
Для этого можно использовать следующий код:
import 'dart:typed_data';
import 'dart:ui' as ui;
import 'package:flutter/material.dart';
import 'package:http/http.dart' as http;
import 'flood_fill_raster.dart';
class FloodFillRasterScreen extends StatelessWidget {
const FloodFillRasterScreen({super.key});
@override
Widget build(BuildContext context) {
return Scaffold(
appBar: AppBar(
title: const Text('Flood Fill Raster'),
),
body: const Center(child: FloodFillRaster()),
);
}
}
class FloodFillRaster extends StatefulWidget {
const FloodFillRaster({super.key});
@override
State<FloodFillRaster> createState() => _FloodFillRasterState();
}
class _FloodFillRasterState extends State<FloodFillRaster> {
ui.Image? _image;
@override
void initState() {
super.initState();
_loadImage().then((image) {
setState(() {
_image = image;
});
});
}
Future<ui.Image> _loadImage() async {
const url =
'https://sun9-77.userapi.com/impg/BiGYCxYxSuZgeILSzA0dtPcNC7935fdhpW36rg/e3jk6CqTwkw.jpg?size=1372x1372&quality=95&sign=2afb3d42765f8777879e06c314345303&type=album';
final response = await http.get(Uri.parse(url));
final Uint8List data = response.bodyBytes;
final ui.Codec codec = await ui.instantiateImageCodec(data.buffer.asUint8List());
final ui.FrameInfo fi = await codec.getNextFrame();
return fi.image;
}
void _onTapDown(TapDownDetails details) async {
final Offset localPosition = details.localPosition;
final int x = localPosition.dx.toInt();
final int y = localPosition.dy.toInt();
const ui.Color newColor = Colors.red;
final image = await ImageFloodFillImpl(_image!).fill(x, y, newColor);
setState(() {
_image = image;
});
}
@override
Widget build(BuildContext context) {
if (_image == null) {
return const Center(
child: CircularProgressIndicator(),
);
}
return FittedBox(
child: GestureDetector(
onTapDown: _onTapDown,
child: CustomPaint(
size: Size(_image!.width.toDouble(), _image!.height.toDouble()),
painter: ImagePainter(_image!),
),
),
);
}
}
class ImagePainter extends CustomPainter {
final ui.Image image;
const ImagePainter(this.image);
@override
void paint(Canvas canvas, Size size) {
canvas.drawImage(image, Offset.zero, Paint()..filterQuality = FilterQuality.high);
}
@override
bool shouldRepaint(ImagePainter oldDelegate) => true;
}Пояснения:
Для выполнения запроса на получение картинки по url используется библиотека http.
Реализации алгоритмов лежат в отдельном файле, поэтому также импортируем содержимое
import 'flood_fill_raster.dart';Для отрисовки
ui.Imageиспользуется виджетCustomPaint.Для хендлинга нажатия на картинку используется
GestureDetector.
В данном примере показана реализация ImageFloodFillQueueImpl. Так же все ок с ImageFloodFillSpanImpl.
При использовании ImageFloodFillImpl, где реализована обычная рекурсия, появляются ошибки, в природе которых я уже не стал разбираться:
Таким образом, в конце концов сравним скорость закрашивания у обоих из оставшихся рабочих алгоритмов путем нажатия на одну точку изображения:
void _onTapDown(TapDownDetails details) async {
final Offset localPosition = details.localPosition;
final int x = localPosition.dx.toInt();
final int y = localPosition.dy.toInt();
const ui.Color newColor = Colors.red;
final Stopwatch stopwatchQueue = Stopwatch()..start();
await ImageFloodFillQueueImpl(_image!).fill(x, y, newColor);
stopwatchQueue.stop();
print('Queue: ${stopwatchQueue.elapsedMilliseconds} ms');
final Stopwatch stopwatchSpan = Stopwatch()..start();
await ImageFloodFillSpanImpl(_image!).fill(x, y, newColor);
stopwatchSpan.stop();
print('Span: ${stopwatchSpan.elapsedMilliseconds} ms');
// setState(() {
// _image = image;
// });
}А также добавим замер скорости выполнения в библиотеке floodfill_image в методе fill
void fill(Offset position) async {
final date_0 = DateTime.now();
int pX = position.dx.toInt();
int pY = position.dy.toInt();
if (_filler == null) return;
if (pX < 0 || pY < 0) return;
int touchColor = _filler!.image!.getPixelSafe(pX, pY);
if (_checkAvoidColor(touchColor)) return;
if (onFloodFillStart != null) onFloodFillStart!(position, image);
_filler?.setTargetColor(touchColor);
await _filler!.floodFill(pX, pY);
ui.decodeImageFromPixels(
_filler!.image!.getBytes(),
_filler!.image!.width,
_filler!.image!.height,
ui.PixelFormat.rgba8888,
(output) async {
image = output;
final date_1 = DateTime.now();
print('Flood fill time: ${date_1.difference(date_0).inMilliseconds} ms');
notifier!.value = position.toString() + touchColor.toString();
if (onFloodFillEnd != null) onFloodFillEnd!(output);
},
);
}И поправим экран:
class FloodFillRasterScreen extends StatelessWidget {
const FloodFillRasterScreen({super.key});
@override
Widget build(BuildContext context) {
return Scaffold(
appBar: AppBar(
title: const Text('Flood Fill Raster'),
),
body: const SingleChildScrollView(
child: Column(
children: [
FloodFillRaster(),
FittedBox(
child: FloodFillImage(
imageProvider: NetworkImage(
'https://sun9-77.userapi.com/impg/BiGYCxYxSuZgeILSzA0dtPcNC7935fdhpW36rg/e3jk6CqTwkw.jpg?size=1372x1372&quality=95&sign=2afb3d42765f8777879e06c314345303&type=album'),
fillColor: Colors.red,
avoidColor: [Colors.black],
tolerance: 50,
),
),
],
)),
);
}
}Результат:
Первые три строки - время закрашивания больших областей. Нижние - относительно маленьких областей.
Span и библиотечная реализация ведут себя примерно одинаково, Queue - отстает при закрашивании больших областей.
Итоги
Сегодня мы рассмотрели, как можно реализовать раскраску растровых изображений с помощью алгоритма flood fill, воспользовались услугами ChatGPT для написания кода, и провели сравнения готовой реализации алгоритма в библиотеке floodfill_image с нашей.
Я надеюсь, что данная статья кому-нибудь дала еще несколько идей, как можно использовать ChatGPT в своей работе.
