Flood fill , также называемый начальным заполнением , представляет собой алгоритм заливки , который определяет и изменяет область , подключенную к данному узлу в многомерном массиве с некоторым совпадающим атрибутом. Он используется в инструменте заливки «ведро» в программах рисования для заполнения связанных областей одинакового цвета другим цветом, а также в таких играх, как Go и Minesweeper, для определения того, какие части очищены. Вариант, называемый заливкой границ, использует те же алгоритмы, но определяется как область , соединенная с данным узлом и не имеющая определенного атрибута. [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 заполнить ( x , y ): если не Внутри ( x , y ), то верните let s = новый пустой стек или очередь Добавьте ( x , y ) к s , пока s не пусто: Удалите ( x , y ) из s , пусть lx = x, а внутри ( lx - 1, y ): Set ( lx - 1, y ) lx = lx - 1 while Внутри ( x , y ): Set ( x , y ) x = x + 1 сканирование ( lx , x - 1, y + 1, s ) сканирование ( lx , x - 1, y - 1, s )сканирование fn ( lx , rx , y , s ): let span_added = false для x в lx .. rx : если не Внутри ( x , y ): span_added = false , иначе если не span_added : Добавьте ( x , y ) к s span_added = true
Со временем были реализованы следующие оптимизации:
Окончательный вариант заполнителя интервалов с комбинированным сканированием и заполнением был опубликован в 1990 году. В форме псевдокода: [8]
fn заполнить ( x , y ): если не Внутри ( x , y ), то верните let s = новая пустая очередь или стек Добавьте ( x , x , y , 1) к s Добавьте ( x , x , y - 1, -1) к s , пока s не пусто: Удалите ( x1 , x2 , y , dy ) из s , пусть x = x1 if Inside ( x , y ): while Внутри ( x - 1, y ): Set ( x - 1, y ) x = x - 1 если х < х1 : Добавьте ( x , x1 - 1, y - dy , - dy ) к s, пока x1 <= x2 : внутри ( x1 , y ): Set ( 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
Два распространенных способа заставить алгоритмы на основе диапазона и пикселей поддерживать заполнение шаблоном — либо использовать уникальный цвет в качестве простой заливки, а затем заменить его шаблоном, либо отслеживать (в двухмерном логическом массиве или в виде областей), какие пиксели были посещены, используя его для обозначения того, что пиксели больше не подлежат заполнению. Затем 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 (установить значения в ноль)установите для возврата и findloop значение falseпока передний пиксель пуст, сделайте двигаться впередзакончиться, покаперейти к СТАРТуОСНОВНОЙ ЦИКЛ: двигаться вперед если правый пиксель находится внутри , то если обратный путь равен true , а findloop имеет значение false и либо передний пиксель , либо левый пиксель находятся внутри , тогда установите для findloop значение true конец, если Поверните направоКРАСКА: двигаться вперед конец, еслиНАЧИНАТЬ: установите счетчик равным количеству заполненных недиагонально соседних пикселей (ТОЛЬКО спереди/сзади/слева/справа), если счетчик не равен 4 , то выполните Поверните направо пока передний пиксель внутри, делай Поверните налево пока передний пиксель не находится внутри, конец, если счетчик переключений Дело 1 если возврат верен , то установите для findloop значение true иначе, если findloop истинен , то если метка равна нулю , тогда восстановить отметку end if else, если передний левый пиксель и задний левый пиксель оба внутри, тогда четкая отметка установить Cur перейти к КРАСКЕ конец, если конец дела случай 2 если задний пиксель не внутри , то если передний левый пиксель внутри , то четкая отметка установить Cur перейти к КРАСКЕ конец, если еще, если отметка не установлена , то установить отметку на лечение установить mark-dir в cur-dir очистить отметку 2 установите findloop и вернитесь в false иначе , если mark2 не установлен , тогда , если cur находится на отметке , тогда , если cur-dir совпадает с mark-dir , тогда четкая отметка повернись установить Cur перейти к КРАСКЕ еще установите для возврата значение true установите для findloop значение false установите cur-dir на mark-dir end if else, если findloop истинен , тогда установите для mark2 значение cur установите mark2-dir в cur-dir конец, если иначе , если курсор находится на отметке , тогда установить Cur на mark2 установите cur-dir на mark2-dir четкая отметка и отметка2 установите для возврата значение false повернись установить Cur перейти к КРАСКЕ иначе , если курить на отметке 2 , тогда установить отметку на лечение установите cur-dir и mark-dir в mark2-dir очистить отметку 2 конец, если конец, если конец, если конец дела случай 3 четкая отметка установить Cur перейти к КРАСКЕ конец дела случай 4 установить Cur сделанный конец дела концевой выключательконец ОСНОВНОГО ЦИКЛА
Версия 0.46 Inkscape включает в себя инструмент заполнения корзины, который дает результат, аналогичный обычным операциям с растровыми изображениями, и действительно использует его: холст визуализируется, операция заливки выполняется в выбранной области, а затем результат отслеживается обратно до пути. Он использует концепцию граничного условия .