Заливка  — это алгоритм, определяющий область, «связанную» с определённым элементом в многомерном массиве. Алгоритм применяется в графических программах, чтобы определить область, которую следует заполнить определённым цветом.Алгоритм рекурсивной заливки:Алгоритм имеет три входных параметра: стартовый элемент, заменяемый цвет и цвет заливки. Отыскиваются все элементы массива, связанные со стартовым путём заменяемого цвета, и перекрашиваются в цвет заливки. Вариантов реализации достаточно много, но все они так или иначе используют очередь или стек. Псевдокод простейшего рекурсивного алгоритма, в котором связность в двумерном массиве определяется по 4 направлениям:Другие способы реализации:Вышеприведённая реализация проста для понимания, но практически не применима в случаях, когда глубина рекурсии жёстко ограничена.Следующий псевдокод показывает реализацию, основанную на применении очереди в явном виде. Она не очень эффективна, но может быть быстро закодирована, не использует стек и удобно отлаживается:Наиболее практичные методики оптимизируют использование стека или очереди, вводя цикл по «западному» и «восточному» направлениям:7. Смещать w на запад до тех пор, пока цвет w не станет отличаться от цвета заменяемый цвет.8. Смещать e на восток до тех пор, пока цвет e не станет отличаться от цвета заменяемый цвет.Если прописать в алгоритм использование отдельного массива для хранения формы области, это позволит обобщить его на случай нечёткого заполнения, когда элементы могут в некоторых пределах отличаться от исходно заданного. Использование этого дополнительного массива в качестве альфа-канала позволяет создать плавный переход на границах между залитой и не залитой областями.Метод заливки, реализуемый в ограниченном объёме памяти:Есть метод, практически не использующий дополнительной памяти для связных по 4 направлениям областей. Таким же методом возможно искать выход из лабиринта. Представьте себе маляра, который красит область так, чтобы не оказаться зажатым окрашенной частью в углу. Начальные границы - это четыре пикселя, которые маляр рассматривает, чтобы выбрать одно из возможных действий. Основные возможные состояния:При продолжении границы используется метод правой руки. Маляр обходит область, держа правую руку на «стене» и продвигается, не отрывая руки.В случае 2 существует путь из области наружу. Маляр красит пиксель, на котором стоял, и движется по этому пути.В случае 3 два граничных пикселя создают полосу, которая, если мы покрасим текущий пиксель, может отрезать нас от всего, что находится по её другую сторону. Нужно закрепить стрелку , указывающую, где мы сейчас и куда смотрим, чтобы, если мы когда-то вернёмся на этот пиксель, мы могли её увидеть. Если такая стрелка уже нарисована, мы её сохраняем и движемся дальше по правилу правой руки.Стрелка на первой двухпиксельной границе фиксирует, где маляр начал работу и куда оттуда пошёл. Если маляр встречает ту же метку, двигаясь в том же направлении, то он понимает, что красить этот квадрат, двигаясь в этом направлении, безопасно: пиксели на другой стороне по какому-то пока не известному пути будут доступны для окраски в будущем. Метка снимается, и её можно поставить где-то ещё.Если же маляр встречает стрелку, указывающую не туда, куда он идёт, значит, он прошёл каким-то путём, возвратившим его к метке. Эту петлю надо исключить. Метка убирается, а маляр движется в указанном ею направлении, руководствуясь правилом левой руки. Так он идёт, пока не попадёт на пересечение. Не отрывая левой руки, маляр ищет простой проход. Найдя его, он красит этот пиксель; петля разрывается, и можно продолжать алгоритм.В случае 4 мы должны проверить противоположные связные по 8 направлениям углы на то, окрашены они или нет. Если хотя бы один из этих двух углов окрашен, получается пересечение многих путей, которое мы окрасить не сможем. Если оба пусты, можем окрасить текущий пиксель и следовать дальше по правилу правой руки.Алгоритм даёт выигрыш в памяти за счёт проигрыша по времени. Для областей простой формы он весьма эффективен, но в более сложных случаях много времени тратится на то, чтобы отследить границы области и убедиться, что всё можно окрасить.Первая коммерческая реализация этого алгоритма появилась в 1981 г. на системе Vicom Image Processing, выпущенной Vicom Systems, Inc. Также в этой системе присутствовал и классический рекурсивный алгоритм.Метод сканирования строк:Алгоритм можно ускорить, заливая сразу линиями. Вместо помещения в стек координат каждого из возможных будущих пикселей рассматриваются соседние строки, и в них определяются смежные сегменты, которые при следующем проходе можно залить; координаты вталкиваются в стек. В большинстве случаев построчный алгоритм на порядок быстрее попиксельного. Его достоинство в том, что каждый пиксель проверяется только один раз.В векторной графике:Программа Inkscape версии 0.46 предоставляет инструмент заливки «ведром», выглядящий как обычная растровая операция и в действительности её применяющий: изображение отрисовывается, применяется заливка выбранной области, и её результат преобразуется обратно в кривые. При этом используется концепция граничных условий.Поведение при больших масштабах:Ссылки: