Заливка , также называемая заливкой семян , представляет собой алгоритм заливки , который определяет и изменяет область, связанную с заданным узлом в многомерном массиве с некоторым соответствующим атрибутом. Он используется в инструменте заливки «ведро» программ рисования для заполнения связанных, схоже окрашенных областей другим цветом, а в таких играх, как Го и Сапер, для определения того, какие элементы очищаются. Вариант, называемый заливкой границ, использует те же алгоритмы, но определяется как область, связанная с заданным узлом, которая не имеет определенного атрибута. [1]
Обратите внимание, что заливка не подходит для рисования заполненных полигонов, так как она пропустит некоторые пиксели в более острых углах. [2] Вместо этого см. правило четного-нечетного и правило ненулевого числа .
Традиционный алгоритм заливки принимает три параметра: начальный узел, целевой цвет и цвет замены. Алгоритм ищет все узлы в массиве, которые соединены с начальным узлом путем целевого цвета, и меняет их на цвет замены. Для заливки границы вместо целевого цвета будет предоставлен цвет границы.
Чтобы обобщить алгоритм общепринятым образом, в следующих описаниях вместо этого будут доступны две подпрограммы. [3] Одна вызывается , Insideкоторая возвращает true для незаполненных точек, которые по цвету находятся внутри заполненной области, и одна вызывается Set, которая заполняет пиксель/узел. Любой узел, который Setвызвал его, больше не должен быть Inside.
В зависимости от того, считаем ли мы узлы, соприкасающиеся в углах, соединенными или нет, у нас есть два варианта: восьмисторонний и четырехсторонний соответственно.
Самая ранняя известная реализация неявно стековой рекурсивной четырехсторонней заливки выглядит следующим образом: [4] [5] [6] [7]
Заливка (узел): 1. Если узел не находится внутри, возврат. 2. Установите узел 3. Выполните заливку на один шаг южнее узла . 4. Выполните заливку на один шаг к северу от узла 5. Выполните заливку на один шаг к западу от узла 6. Выполните заливку на один шаг к востоку от узла 7. Возвращение.
Несмотря на простоту понимания, реализация использованного выше алгоритма непрактична в языках и средах, где пространство стека сильно ограничено (например, микроконтроллеры ).
Перемещение рекурсии в структуру данных ( стек или очередь ) предотвращает переполнение стека . Это похоже на простое рекурсивное решение, за исключением того, что вместо выполнения рекурсивных вызовов оно помещает узлы в стек или очередь для потребления, при этом выбор структуры данных влияет на шаблон распространения:
Заливка (узел): 1. Установите Q в пустую очередь или стек.2. Добавьте узел в конец Q. 3. Пока Q не пусто: 4. Присвойте n значение первому элементу Q. 5. Удалить первый элемент из Q. 6. Если n находится внутри : установите n . Добавьте узел к западу от n в конец Q. Добавьте узел к востоку от n к концу Q. Добавьте узел к северу от n к концу Q. Добавьте узел к югу от n к концу Q. 7. Продолжайте цикл, пока Q не будет исчерпан. 8. Возвращение.
Можно оптимизировать вещи еще больше, работая в первую очередь с интервалами, строкой с константой y. Первый опубликованный полный пример работает по следующему базовому принципу. [1]
lxи самую правую заполненную точку rx. Это определяет диапазон.lxсверху rxи снизу исходной точки в поисках новых исходных точек для продолжения.В качестве оптимизации алгоритм сканирования не требует перезапуска с каждой исходной точки, а только с тех, которые находятся в начале следующего диапазона. Использование стека сначала исследует диапазоны в глубину, тогда как очередь сначала исследует диапазоны в ширину.
fn fill ( x , y ): если не Внутри ( x , y ), то вернуть пусть s = новый пустой стек или очередь Добавить ( x , y ) к s, пока s не пусто: Удалить ( x , y ) из s, пусть lx = x, а внутри ( lx - 1, y ): Установить ( lx - 1, y ) lx = lx - 1 в то время как Внутри ( x , y ): Установить ( x , y ) x = x + 1 сканировать ( lx , x - 1, y + 1, s ) сканировать ( lx , x - 1, y - 1, s )fn сканирование ( lx , rx , y , s ): пусть span_added = false для x в lx .. rx : если не Внутри ( x , y ): span_added = false иначе, если не span_added : Добавить ( x , y ) к s span_added = true
Со временем были реализованы следующие оптимизации:
Окончательный вариант комбинированного заполнителя интервалов сканирования и заполнения был опубликован в 1990 году. В виде псевдокода: [8]
fn fill ( x , y ): если не Внутри ( x , y ), то вернуть пусть s = новая пустая очередь или стек Добавить ( x , x , y , 1) к s Добавить ( x , x , y - 1, -1) к s , пока s не пусто: Удалим ( x1 , x2 , y , dy ) из s, пусть x = x1, если внутри ( x , y ): в то время как Внутри ( x - 1, y ): Установить ( x - 1, y ) x = x - 1 если х < х1 : Добавить ( x , x1 - 1, y - dy , - dy ) к s, пока x1 <= x2 : в то время как Внутри ( x1 , y ): Установить ( x1 , y ) x1 = x1 + 1 if x1 > x : добавьте ( x , x1 - 1, y + dy , dy ) к s если x1 - 1 > x2 : добавьте ( x2 + 1, x1 - 1, y - dy , - dy ) к s x1 = x1 + 1 пока x1 < x2 и не Внутри ( x1 , y ): x1 = x1 + 1 x = x1
Два распространенных способа заставить алгоритмы span и pixel-based поддерживать заполнение шаблоном — это либо использовать уникальный цвет в качестве простой заливки, а затем заменить его шаблоном, либо отслеживать (в двумерном логическом массиве или в виде областей), какие пиксели были посещены, используя это для указания того, что пиксели больше не заполняются. Затем Inside должен возвращать false для таких посещенных пикселей. [3]
Некоторые теоретики применили явную теорию графов к этой проблеме, рассматривая промежутки пикселей или их совокупности как узлы и изучая их связность. Первый опубликованный алгоритм теории графов работал аналогично заполнению промежутков, описанному выше, но имел способ обнаружения дублирования заполнения промежутков. [9] К сожалению, в нем были ошибки, из-за которых он не мог завершить некоторые заполнения. [10] Позднее был опубликован исправленный алгоритм с похожей основой в теории графов; однако он изменяет изображение по мере его продвижения, чтобы временно блокировать потенциальные циклы, усложняя программный интерфейс. [10] Более поздний опубликованный алгоритм зависел от того, чтобы граница отличалась от всего остального на изображении, и поэтому не подходит для большинства применений; [11] [3] он также требует дополнительного бита на пиксель для учета. [3]
Существует метод, который практически не использует память для четырехсвязных областей, притворяясь художником, пытающимся закрасить область, не загоняя себя в угол. Это также метод решения лабиринтов . Четыре пикселя, составляющие первичную границу, исследуются, чтобы определить, какое действие следует предпринять. Художник может оказаться в одном из нескольких состояний:
Если необходимо следовать пути или границе, используется правило правой руки. Художник следует области, положив правую руку на стену (границу области) и продвигаясь по краю области, не убирая руку.
В случае №1 художник закрашивает (заполняет) пиксель, на котором он стоит, и останавливает алгоритм.
Для случая №2 существует путь, ведущий из области. Закрасьте пиксель, на котором стоит художник, и двигайтесь в направлении открытого пути.
Для случая №3 два граничных пикселя определяют путь, который, если мы закрасили текущий пиксель, может помешать нам вернуться на другую сторону пути. Нам нужна «метка», чтобы определить, где мы находимся и в каком направлении движемся, чтобы увидеть, вернемся ли мы когда-нибудь к тому же самому пикселю. Если мы уже создали такую «метку», то мы сохраняем нашу предыдущую метку и переходим к следующему пикселю, следуя правилу правой руки.
Метка используется для первой встреченной границы в 2 пикселя, чтобы запомнить, где начался проход и в каком направлении двигался художник. Если метка встречается снова, а художник движется в том же направлении, то художник знает, что можно безопасно закрасить квадрат с меткой и продолжить в том же направлении. Это происходит потому, что (через какой-то неизвестный путь) пиксели по другую сторону метки могут быть достигнуты и закрашены в будущем. Метка удаляется для будущего использования.
Если художник сталкивается с меткой, но движется в другом направлении, то произошел какой-то цикл, который заставил художника вернуться к метке. Этот цикл должен быть устранен. Метка подбирается, и художник затем продолжает в направлении, указанном ранее меткой, используя правило левой руки для границы (похожее на правило правой руки, но используя левую руку художника). Это продолжается до тех пор, пока не будет найдено пересечение (с тремя или более открытыми граничными пикселями). Все еще используя правило левой руки, художник теперь ищет простой проход (созданным двумя граничными пикселями). После нахождения этого двухпиксельного граничного пути этот пиксель закрашивается. Это прерывает цикл и позволяет алгоритму продолжить работу.
Для случая №4 нам нужно проверить противоположные 8-связанные углы, чтобы увидеть, заполнены они или нет. Если заполнен один или оба, то это создает многопутевое пересечение и не может быть заполнено. Если оба пусты, то текущий пиксель может быть закрашен, и художник может двигаться, следуя правилу правой руки.
Алгоритм тратит время на память. Для простых форм он очень эффективен. Однако если форма сложная и имеет много особенностей, алгоритм тратит много времени на трассировку краев области, пытаясь убедиться, что все можно покрасить.
Алгоритм ходьбы был опубликован в 1994 году. [12]
Это псевдокодовая реализация оптимального алгоритма заполнения фиксированной памяти, написанная на структурированном английском языке:
cur, mark, и mark2каждый из них содержит либо координаты пикселей, либо нулевое значениеmarkустановлено значение null, не стирайте его предыдущее значение координат. Сохраните эти координаты доступными для вызова при необходимости.cur-dir, mark-dir, и mark2-dirкаждый из них удерживает направление (влево, вправо, вверх или вниз)backtrackи findloopкаждый из них содержит булевы значенияcountэто целое числоcur-dirустановить cur на начальный пиксельустановить cur-dir в направление по умолчаниюочистить отметку и отметку2 (установить значения на ноль)установите backtrack и findloop на falseпока передний пиксель пуст, делайте двигаться впередконец, покаперейти к СТАРТУОСНОВНОЙ ЦИКЛ: двигаться вперед если правый пиксель находится внутри, то если backtrack имеет значение true , а findloop имеет значение false и либо передний , либо левый пиксель находится внутри , то установите findloop в значение true конец, если Поверните направоКРАСКА: двигаться вперед конец, еслиНАЧИНАТЬ: установить счетчик равным количеству заполненных пикселей, не смежных по диагонали (ТОЛЬКО спереди/сзади/слева/справа), если счетчик не равен 4 , то сделать Поверните направо пока передний пиксель находится внутри, сделайте Поверните налево пока передний пиксель не находится внутри конца, если количество переключателей случай 1 если обратный отскок истинен, то установите findloop в значение true иначе если findloop равен true , то если mark равен null , то восстановить отметку конец если иначе если передний левый пиксель и задний левый пиксель оба находятся внутри тогда четкая отметка установить текущий перейти к КРАСКЕ конец, если конец дела случай 2 если задний пиксель не внутри , то если передний левый пиксель внутри , то четкая отметка установить текущий перейти к КРАСКЕ конец если иначе если отметка не установлена тогда установить отметку на текущую установить mark-dir в cur-dir четкая отметка2 установите findloop и backtrack на false иначе если mark2 не установлен , то если cur равен mark , то если cur-dir совпадает с mark-dir , то четкая отметка повернись установить текущий перейти к КРАСКЕ еще установить возврат к истине установите findloop на false установить cur-dir в mark-dir конец если иначе если findloop истинен тогда установить mark2 на cur установить mark2-dir в cur-dir конец если иначе если cur находится на отметке тогда установить cur на mark2 установить cur-dir в mark2-dir четкая отметка и отметка2 установить возврат на ложь повернись установить текущий перейти к КРАСКЕ иначе если cur на отметке2 тогда установить отметку на текущую установите cur-dir и mark-dir на mark2-dir четкая отметка2 конец, если конец, если конец, если конец дела случай 3 четкая отметка установить текущий перейти к КРАСКЕ конец дела случай 4 установить текущий сделанный конец дела концевой выключательконец ГЛАВНОГО ЦИКЛА
Версия 0.46 Inkscape включает инструмент заливки бакета, дающий вывод, аналогичный обычным операциям с растровыми изображениями, и действительно использующий его: холст визуализируется, операция заливки выполняется на выбранной области, а затем результат трассируется обратно к пути. Он использует концепцию граничного условия .