Интернет магазин китайских планшетных компьютеров

Компьютеры - Заливка

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

Алгоритм

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

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

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

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

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

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

 Заливка:
 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 можно встретить края массива}

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