Заливка

Зали́вка (иногда уточняют «методом „наводнение“», от англ. flood fill) — алгоритм, определяющий область, «связанную» с определённым элементом в многомерном массиве (как правило, это двумерный массив точек растрового изображения). Алгоритм применяется в графических программах, чтобы определить область, которую следует заполнить определённым цветом.

Алгоритм рекурсивной заливки

Рекурсивная заливка со связностью по 4 направлениям (в окрестности фон Неймана)

Рекурсивная заливка со связностью по 8 направлениям (в окрестности Мура)

Алгоритм имеет три входных параметра: стартовый элемент, заменяемый цвет и цвет заливки. Отыскиваются все элементы массива, связанные со стартовым путём заменяемого цвета, и перекрашиваются в цвет заливки. Вариантов реализации достаточно много, но все они так или иначе используют очередь или стек. Псевдокод простейшего рекурсивного алгоритма, в котором связность в двумерном массиве определяется по 4 направлениям:

 Заливка (элемент, заменяемый цвет, цвет заливки):
 1. Если цвет элемента не заменяемый цвет, возврат.
 2. Установить цвет элемента в цвет заливки.
 3. Заливка (шаг на запад от элемента, заменяемый цвет, цвет заливки).
    Заливка (шаг на восток от элемента, заменяемый цвет, цвет заливки).
    Заливка (шаг на север от элемента, заменяемый цвет, цвет заливки).
    Заливка (шаг на юг от элемента, заменяемый цвет, цвет заливки).
    {для связности по 8 направлениям - ещё четыре вызова по диагоналям}
 4. Возврат.

Другие способы реализации

Вышеприведённая реализация проста для понимания, но практически не применима в случаях, когда глубина рекурсии жёстко ограничена (напр. в апплетах на Java).

Следующий псевдокод показывает реализацию, основанную на применении очереди в явном виде. Она не очень эффективна, но может быть быстро закодирована, не использует стек и удобно отлаживается:

 Заливка (элемент, заменяемый цвет, цвет заливки):
 1. Присвоить q пустую очередь.
 2. Если цвет элемента - не заменяемый цвет, возврат.
 3. Поместить элемент в конец Q.
 4. До тех пор, пока Q не пуста: 
 5.     Присвоить n первый элемент Q
 6.     Если цвет n - заменяемый цвет, установить его в цвет заливки.
 7.     Вытолкнуть первый элемент из Q
 8.     Если цвет элемента к западу от n - заменяемый цвет:
 9.         Установить цветом этого элемента цвет заливки
10.         Поместить этот элемент в конец Q
{11 - 19.   То же самое для остальных соседей}
20. Возврат.

Наиболее практичные методики оптимизируют использование стека или очереди, вводя цикл по «западному» и «восточному» направлениям:

 Заливка (элемент, заменяемый цвет, цвет заливки):
 1. Присвоить Q пустую очередь.
 2. Если цвет элемента - не заменяемый цвет, возврат.
 3. Поместить элемент в Q.
 4. Для каждого N из элементов Q:
 5.  Если цвет N - заменяемый цвет:
 6.   Присвоить w и e тот же элемент, что и N.
 7.   Смещать w на запад до тех пор, пока цвет w не станет отличаться от цвета "заменяемый цвет" .
 8.   Смещать e на восток до тех пор, пока цвет e не станет отличаться от цвета "заменяемый цвет".
 9.   Всем элементам между w и e придать цвет заливки.
10.   Для каждого n между w и e:
11.    Если цвет элемента к северу от n - заменяемый цвет, поместить этот элемент в Q.
       Если цвет элемента к югу от n - заменяемый цвет, поместить этот элемент в Q.
12. Продолжать цикл, пока в Q останутся элементы.
13. Возврат. {разумеется, в пп. 7, 8, а также 11 можно встретить края массива}

Если прописать в алгоритм использование отдельного массива для хранения формы области, это позволит обобщить его на случай «нечёткого» заполнения, когда элементы могут в некоторых пределах отличаться от исходно заданного. Использование этого дополнительного массива в качестве альфа-канала позволяет создать плавный переход на границах между залитой и не залитой областями.

Метод заливки, реализуемый в ограниченном объёме памяти (метод правой руки)

Есть метод, практически не использующий дополнительную память для связных по 4 направлениям (см. Окрестность фон Неймана) областей. Таким же методом возможно искать выход из лабиринта. Представьте себе маляра, который красит область так, чтобы не оказаться зажатым окрашенной частью в углу. Начальные границы — это четыре пикселя, которые маляр рассматривает, чтобы выбрать одно из возможных действий. Основные возможные состояния:

1. Все 4 граничных пикселя окрашены.
2. Три граничных пикселя окрашены.
3. Два граничных пикселя окрашены.
4. Один граничный пиксель окрашен.
5. Ни один из граничных пикселе не окрашен.

При продолжении границы используется метод правой руки. Маляр обходит область, держа правую руку на «стене» (границе области) и продвигается, не отрывая руки.

В случае 1 маляр окрашивает пиксель, на котором стоял, и улетает (алгоритм завершён).

В случае 2 существует путь из области наружу. Маляр красит пиксель, на котором стоял, и движется по этому пути.

В случае 3 два граничных пикселя создают полосу, которая, если мы покрасим текущий пиксель, может отрезать нас от всего, что находится по её другую сторону. Нужно закрепить «стрелку», указывающую, где мы сейчас и куда смотрим, чтобы, если мы когда-то вернёмся на этот пиксель, мы могли её увидеть. Если такая стрелка уже нарисована, мы её сохраняем и движемся дальше по правилу правой руки.

Стрелка на первой двухпиксельной границе фиксирует, где маляр начал работу и куда оттуда пошёл. Если маляр встречает ту же метку, двигаясь в том же направлении, то он понимает, что красить этот квадрат, двигаясь в этом направлении, безопасно: пиксели на другой стороне по какому-то пока не известному пути будут доступны для окраски в будущем. Метка снимается, и её можно поставить где-то ещё.

Если же маляр встречает стрелку, указывающую не туда, куда он идёт, значит, он прошёл каким-то путём, возвратившим его к метке. Эту петлю надо исключить. Метка убирается, а маляр движется в указанном ею направлении, руководствуясь правилом левой руки. Так он идёт, пока не попадёт на пересечение (с не менее чем тремя пикселями открытой границы). Не отрывая левой руки, маляр ищет простой проход (состоящий из двух граничных пикселей). Найдя его, он красит этот пиксель; петля разрывается, и можно продолжать алгоритм.

В случае 4 мы должны проверить противоположные связные по 8 направлениям углы на то, окрашены они или нет. Если хотя бы один из этих двух углов окрашен, получается пересечение многих путей, которое мы окрасить не сможем. Если оба пусты, можем окрасить текущий пиксель и следовать дальше по правилу правой руки.

Алгоритм даёт выигрыш в памяти за счёт проигрыша по времени. Для областей простой формы он весьма эффективен, но в более сложных случаях много времени тратится на то, чтобы отследить границы области и убедиться, что всё можно окрасить.

Первая коммерческая реализация этого алгоритма появилась в 1981 году на системе Vicom Image Processing, выпущенной Vicom Systems, Inc. Также в этой системе присутствовал и классический рекурсивный алгоритм.

Метод сканирования строк

Анимация построчной заливки

Алгоритм можно ускорить, заливая сразу линиями. Вместо помещения в стек координат каждого из возможных будущих пикселей рассматриваются соседние строки (одной выше и одной ниже), и в них определяются смежные сегменты, которые при следующем проходе можно залить; координаты (либо начало, либо конец) вталкиваются в стек. В большинстве случаев построчный алгоритм на порядок быстрее попиксельного. Его достоинство в том, что каждый пиксель проверяется только один раз.

В векторной графике

Программа Inkscape начиная с версии 0.46 предоставляет инструмент заливки «ведром», выглядящий как обычная растровая операция и в действительности её применяющий: изображение со сплошной границей заливается, далее результат заливки преобразуется в векторный вид.

См. также

• Поиск в ширину
• Поиск в глубину
• Алгоритм Дейкстры

Ссылки

• Sample implementations for recursive and non-recursive, classic and scanline flood fill, by Lode Vandevenne.
• Sample Java implementation using Q non-recursive.