Наводнение

Flood fill , также называемый начальным заполнением , представляет собой алгоритм заливки , который определяет и изменяет область, подключенную к данному узлу в многомерном массиве с некоторым совпадающим атрибутом. Он используется в инструменте заливки «ведро» в программах рисования для заполнения соединенных областей одинакового цвета другим цветом, а также в таких играх, как Go и Minesweeper, для определения того, какие части очищены. Вариант под названием «Заливка границ» использует те же алгоритмы, но определяется как область, соединенная с данным узлом и не имеющая определенного атрибута. ^[1]

Обратите внимание, что заливка заливкой не подходит для рисования заполненных многоугольников, так как в более острых углах будут пропущены некоторые пиксели. ^[2] Вместо этого см. Правило чет-нечет и Правило ненулевого значения .

Параметры алгоритма

Традиционный алгоритм заливки принимает три параметра: начальный узел, целевой цвет и замещающий цвет. Алгоритм ищет все узлы в массиве, которые соединены с начальным узлом путем целевого цвета, и заменяет их цветом замены. Для заливки границ вместо целевого цвета будет указан цвет границы.

Чтобы обобщить алгоритм обычным способом, в следующих описаниях вместо этого будут доступны две процедуры. ^[3] Один позвонил Inside который возвращает true для незаполненных точек, которые по своему цвету находятся внутри заполненной области, и называется Set который заполняет пиксель/узел. Любой узел, имеющий Set призванный, его больше не должно быть Inside.

В зависимости от того, считаем ли мы узлы, соприкасающиеся по углам, соединенными или нет, у нас есть два варианта: восьмисторонний и четырехсторонний соответственно.

Рекурсивная реализация на основе стека (четырехходовая)

Самая ранняя известная реализация неявно основанной на стеке рекурсивной четырехсторонней заливки выглядит следующим образом: ^[4]^[5]^[6]^[7]

Flood-fill (node):
 1. If node is not Inside return.
 2. Set the node
 3. Perform Flood-fill one step to the south of node.
 4. Perform Flood-fill one step to the north of node
 5. Perform Flood-fill one step to the west of node
 6. Perform Flood-fill one step to the east of node
 7. Return.

Хотя реализация алгоритма, использованного выше, проста для понимания, она непрактична в языках и средах, где пространство стека сильно ограничено (например, микроконтроллеры ).

Перемещение рекурсии в структуру данных

Четырехходовая заливка с использованием очереди на хранение

Четырехходовая заливка с использованием штабеля для хранения

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

Flood-fill (node):
  1. Set Q to the empty queue or stack.
  2. Add node to the end of Q.
  3. While Q is not empty:
  4.   Set n equal to the first element of Q.
  5.   Remove first element from Q.
  6.   If n is Inside:
         Set the n
         Add the node to the west of n to the end of Q.
         Add the node to the east of n to the end of Q.
         Add the node to the north of n to the end of Q.
         Add the node to the south of n to the end of Q.
  7. Continue looping until Q is exhausted.
  8. Return.

Дальнейшие потенциальные оптимизации

Проверьте и установите цвет пикселя каждого узла перед добавлением его в стек/очередь, уменьшив размер стека/очереди.
Используйте цикл для направлений восток/запад, ставя в очередь пиксели выше/ниже по мере продвижения (что делает его похожим на алгоритмы заполнения диапазона, показанные ниже).
Чередуйте две или более копии кода с дополнительными стеками/очередями, чтобы предоставить процессорам с нарушением порядка больше возможностей для распараллеливания.
Используйте несколько потоков (в идеале с немного разным порядком посещения, чтобы они не оставались в одной и той же области). ^[6]

Преимущества

Очень простой алгоритм - легко сделать без ошибок. ^[6]

Недостатки

Использует много памяти, особенно при использовании стека. ^[6]
Тестирует наиболее заполненные пиксели в общей сложности четыре раза.
Не подходит для заполнения узором, так как для изменения требуются результаты теста пикселей.
Шаблон доступа не поддерживает кэширование для варианта с очередями.
Невозможно легко оптимизировать многопиксельные слова или битовые плоскости. ^[2]

Заполнение пролета

Можно оптимизировать ситуацию, работая в первую очередь с промежутками, строками с константами. y. Первый опубликованный полный пример работает по следующему основному принципу. ^[1]

Начиная с исходной точки, заполняйте слева и справа. Следите за самой левой заполненной точкой lx и крайняя правая заполненная точка rx. Это определяет диапазон.
Сканировать из lx к rx выше и ниже исходной точки в поисках новых исходных точек, с которыми можно продолжить.

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

fn fill(x, y):
    if not Inside(x, y) then return
    let s = new empty stack or queue
    Add (x, y) to s
    while s is not empty:
        Remove an (x, y) from s
        let lx = x
        while Inside(lx - 1, y):
            Set(lx - 1, y)
            lx = lx - 1
        while Inside(x, y):
            Set(x, y)
            x = x + 1
      scan(lx, x - 1, y + 1, s)
      scan(lx, x - 1, y - 1, s)

fn scan(lx, rx, y, s):
    let span_added = false
    for x in lx .. rx:
        if not Inside(x, y):
            span_added = false
        else if not span_added:
            Add (x, y) to s
            span_added = true

Со временем были реализованы следующие оптимизации:

Когда новое сканирование будет полностью находиться в пределах родительского диапазона, оно, безусловно, найдет только заполненные пиксели, и поэтому не потребуется постановка в очередь. ^[1]^[6]^[3]
Кроме того, когда новое сканирование перекрывает исходный пролет, необходимо сканировать только свесы (U-образные и W-образные повороты). ^[3]
Можно заполнять при сканировании семян. ^[6]

Окончательный вариант заполнителя интервалов с комбинированным сканированием и заполнением был опубликован в 1990 году. В форме псевдокода: ^[8]

fn fill(x, y):
    if not Inside(x, y) then return
    let s = new empty queue or stack
    Add (x, x, y, 1) to s
    Add (x, x, y - 1, -1) to s
    while s is not empty:
        Remove an (x1, x2, y, dy) from s
        let x = x1
        if Inside(x, y):
            while Inside(x - 1, y):
                Set(x - 1, y)
                x = x - 1
            if x < x1:
                Add (x, x1 - 1, y - dy, -dy) to s
        while x1 <= x2:
            while Inside(x1, y):
                Set(x1, y)
                x1 = x1 + 1
            if x1 > x:
                Add (x, x1 - 1, y + dy, dy) to s
            if x1 - 1 > x2:
                Add (x2 + 1, x1 - 1, y - dy, -dy) to s
            x1 = x1 + 1
            while x1 < x2 and not Inside(x1, y):
                x1 = x1 + 1
            x = x1

Преимущества

В 2–8 раз быстрее, чем пиксельно-рекурсивный алгоритм.
Шаблон доступа удобен для кэша и битовой плоскости. ^[6]
Можно рисовать горизонтальную линию, а не задавать отдельные пиксели. ^[6]

Недостатки

По-прежнему посещает уже заполненные пиксели. (Для популярного алгоритма — 3 сканирования большинства пикселей. Для последнего — дополнительное сканирование только тех пикселей, где в заполненной области есть дыры.) ^[3]
Не подходит для заполнения узором, так как для изменения требуются результаты теста пикселей.

Добавление поддержки заполнения узором

Два распространенных способа заставить алгоритмы на основе диапазона и пикселей поддерживать заполнение шаблоном — либо использовать уникальный цвет в качестве простой заливки, а затем заменить его шаблоном, либо отслеживать (в двухмерном логическом массиве или в виде областей), какие пиксели были посещены, используя его для обозначения того, что пиксели больше не подлежат заполнению. Затем Inside должен вернуть false для таких посещенных пикселей. ^[3]

Теоретико-графовое заполнение

Некоторые теоретики применили к этой проблеме явную теорию графов, рассматривая промежутки пикселей или их агрегаты как узлы и изучая их связность. Первый опубликованный алгоритм теории графов работал аналогично заполнению интервалов, описанному выше, но имел возможность определять, когда он будет дублировать заполнение интервалов. ^[9] К сожалению, в нем были ошибки, из-за которых некоторые заливки не выполнялись. ^[10] Позже был опубликован исправленный алгоритм, основанный на аналогичной основе теории графов; однако он изменяет изображение по ходу выполнения, чтобы временно заблокировать потенциальные петли, усложняя программный интерфейс. ^[10] Опубликованный позже алгоритм зависел от того, чтобы граница отличалась от всего остального на изображении, и поэтому не подходил для большинства применений; ^[11]^[3] для бухгалтерского учета также требуется дополнительный бит на пиксель. ^[3]

Преимущества

Подходит для прямого заполнения узором, поскольку никогда не проверяет заполненные пиксели повторно. ^[9]^[10]^[11]
Удвоенная скорость исходного алгоритма интервала для несложных заливок. ^[3]
Шаблон доступа удобен для кэша и битовой плоскости. ^[6]^[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

set cur to starting pixel
set cur-dir to default direction
clear mark and mark2 (set values to null)
set backtrack and findloop to false

while front-pixel is empty do
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is inside then
        if backtrack is true and findloop is false and either front-pixel or left-pixel is inside then
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
    if count is not 4 then
        do
            turn right
        while front-pixel is inside
        do
            turn left
        while front-pixel is not inside
    end if
    switch count
        case 1
            if backtrack is true then
                set findloop to true
            else if findloop is true then
                if mark is null then
                    restore mark
                end if
            else if front-left-pixel and back-left-pixel are both inside then
                clear mark
                set cur
                jump to PAINT
            end if
        end case
        case 2
            if back-pixel is not inside then
                if front-left-pixel is inside then
                    clear mark
                    set cur
                    jump to PAINT
                end if
            else if mark is not set then
                set mark to cur
                set mark-dir to cur-dir
                clear mark2
                set findloop and backtrack to false
            else
                if mark2 is not set then
                    if cur is at mark then
                        if cur-dir is the same as mark-dir then
                            clear mark
                            turn around
                            set cur
                            jump to PAINT
                        else
                            set backtrack to true
                            set findloop to false
                            set cur-dir to mark-dir
                        end if
                    else if findloop is true then
                        set mark2 to cur
                        set mark2-dir to cur-dir
                    end if
                else
                    if cur is at mark then
                        set cur to mark2
                        set cur-dir to mark2-dir
                        clear mark and mark2
                        set backtrack to false
                        turn around
                        set cur
                        jump to PAINT
                    else if cur at mark2 then
                        set mark to cur
                        set cur-dir and mark-dir to mark2-dir
                        clear mark2
                    end if
                end if
            end if
        end case
        case 3
            clear mark
            set cur
            jump to PAINT
        end case
        case 4
            set cur
            done
        end case
    end switch
end MAIN LOOP

Преимущества

Постоянное использование памяти.

Недостатки

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

Векторные реализации

Версия 0.46 Inkscape включает в себя инструмент заполнения корзины, который дает результат, аналогичный обычным операциям с растровыми изображениями, и действительно использует его: холст визуализируется, операция заливки выполняется в выбранной области, а затем результат отслеживается обратно до пути. Он использует концепцию граничного условия .

См. также

Внешние ссылки

Ссылки

^ Перейти обратно: ^а ^б ^с Смит, Элви Рэй (1979). Тоновая заливка . SIGGRAPH '79: Материалы 6-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 276–283. дои : 10.1145/800249.807456 .
^ Перейти обратно: ^а ^б Экланд, Брайан Д; Весте, Нил Х (1981). Алгоритм флага края — метод заливки для дисплеев растрового сканирования . Транзакции IEEE на компьютерах (том: C-30, выпуск: 1). стр. 41–48. дои : 10.1109/TC.1981.6312155 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Фишкин, Кеннет П.; Барский, Брайан А. (1985). Анализ и алгоритм распространения заполнения . Компьютерные изображения: современные исследования графического интерфейса '85. стр. 56–76. дои : 10.1007/978-4-431-68033-8_6 .
^ Ньюман, Уильям М; Спроролл, Роберт Флетчер (1979). Принципы интерактивной компьютерной графики (2-е изд.). МакГроу-Хилл. п. 253. ИСБН 978-0-07-046338-7 .
^ Павлидис, Тео (1982). Алгоритмы обработки графики и изображений Спрингер-Верлаг. п. 181. ИСБН 978-3-642-93210-6 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Левой, Марк (1982). Алгоритмы затопления территории . SIGGRAPH 1981 Конспект курса двумерной компьютерной анимации.
^ Фоли, доктор медицинских наук; ван Дам, А; Файнер, СК; Хьюз, СК (1990). Компьютерная графика: принципы и практика (2-е изд.). Аддисон-Уэсли. стр. 979–982. ISBN 978-0-201-84840-3 .
^ Хекберт, Пол С. (1990). «IV.10: Алгоритм заполнения семян». В Гласснер, Эндрю С. (ред.). Графические драгоценности . Академическая пресса. стр. 275–277. ISBN 0122861663 .
^ Перейти обратно: ^а ^б Либерман, Генри (1978). Как раскрашивать в книжке-раскраске . SIGGRAPH '78: Материалы 5-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 111–116. дои : 10.1145/800248.807380 .
^ Перейти обратно: ^а ^б ^с Шани, Ури (1980). Заполнение областей в двоичных растровых изображениях: теоретико-графовый подход . SIGGRAPH '80: Материалы 7-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 321–327. дои : 10.1145/800250.807511 .
^ Перейти обратно: ^а ^б Павлидис, Тео (1981). Контурная заливка в растровой графике . SIGGRAPH '81: Материалы 8-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 29–36. дои : 10.1145/800224.806786 .
^ Генрих, Доминик (1994). Экономичное заполнение областей в растровой графике . Визуальный компьютер. стр. 205–215. дои : 10.1007/BF01901287 .

[79Smith-1] Перейти обратно: ^а ^б ^с Смит, Элви Рэй (1979). Тоновая заливка . SIGGRAPH '79: Материалы 6-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 276–283. дои : 10.1145/800249.807456 .

[81Ackland-2] Перейти обратно: ^а ^б Экланд, Брайан Д; Весте, Нил Х (1981). Алгоритм флага края — метод заливки для дисплеев растрового сканирования . Транзакции IEEE на компьютерах (том: C-30, выпуск: 1). стр. 41–48. дои : 10.1109/TC.1981.6312155 .

[85Fishkin-3] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Фишкин, Кеннет П.; Барский, Брайан А. (1985). Анализ и алгоритм распространения заполнения . Компьютерные изображения: современные исследования графического интерфейса '85. стр. 56–76. дои : 10.1007/978-4-431-68033-8_6 .

[73Newman-4] Ньюман, Уильям М; Спроролл, Роберт Флетчер (1979). Принципы интерактивной компьютерной графики (2-е изд.). МакГроу-Хилл. п. 253. ИСБН 978-0-07-046338-7 .

[82Pavlidis-5] Павлидис, Тео (1982). Алгоритмы обработки графики и изображений Спрингер-Верлаг. п. 181. ИСБН 978-3-642-93210-6 .

[82Levoy-6] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Левой, Марк (1982). Алгоритмы затопления территории . SIGGRAPH 1981 Конспект курса двумерной компьютерной анимации.

[90Foley-7] Фоли, доктор медицинских наук; ван Дам, А; Файнер, СК; Хьюз, СК (1990). Компьютерная графика: принципы и практика (2-е изд.). Аддисон-Уэсли. стр. 979–982. ISBN 978-0-201-84840-3 .

[90Heckbert-8] Хекберт, Пол С. (1990). «IV.10: Алгоритм заполнения семян». В Гласснер, Эндрю С. (ред.). Графические драгоценности . Академическая пресса. стр. 275–277. ISBN 0122861663 .

[78Lieberman-9] Перейти обратно: ^а ^б Либерман, Генри (1978). Как раскрашивать в книжке-раскраске . SIGGRAPH '78: Материалы 5-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 111–116. дои : 10.1145/800248.807380 .

[80Shani-10] Перейти обратно: ^а ^б ^с Шани, Ури (1980). Заполнение областей в двоичных растровых изображениях: теоретико-графовый подход . SIGGRAPH '80: Материалы 7-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 321–327. дои : 10.1145/800250.807511 .

[81Pavlidis-11] Перейти обратно: ^а ^б Павлидис, Тео (1981). Контурная заливка в растровой графике . SIGGRAPH '81: Материалы 8-й ежегодной конференции по компьютерной графике и интерактивным методам. стр. 29–36. дои : 10.1145/800224.806786 .

[94Henrich-12] Генрих, Доминик (1994). Экономичное заполнение областей в растровой графике . Визуальный компьютер. стр. 205–215. дои : 10.1007/BF01901287 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]