В графических редакторах есть такой инструмент "floodfill", который означает заливку цветом, и обычно его иконка выглядит как ведро, из которого проливается краска:
Собственно, он называется так, потому что может именно залить (как жидкостью) цветом любую область. В прошлом на особо медленных компьютерах процесс заливки можно было наблюдать – цвет действительно как бы разливался, и если где-то находил проход, то проливался и туда, заполняя всё доступное пространство.
Допустим, мы красим оранжевым цветом. Когда мы кликаем в какое-то место изображения, там находится пиксел, например, синего цвета. Заливка работает так, что заменяет начальный синий пиксел на оранжевый, а затем проверяет, есть ли вокруг него ещё такие же синие пикселы. Если они есть, заливка красит и их, затем опять проверяет их соседей и т.д.
Заливка останавливается, когда больше не найдёт пикселов, связанных с предыдущими закрашенными. Иначе говоря – из любого закрашенного пиксела можно прийти в стартовый через соседей.
Не напоминает ли нам это кое-что?
Алгоритм Дейкстры для поиска кратчайшего пути действует очень похоже, тоже как бы заливая жидкостью ближайших соседей текущей точки.
Какие практические применения заливки можно найти, помимо рисования?
Например, я использовал его в своей реализации игры Xonix (картинка не моя):
Игрок должен рисовать замкнутые области. Если внутри области ничего нет, то её можно закрасить. Если там внутри один или несколько шариков, то закрашивать нельзя.
Первоначально я пытался найти решение геометрическими способами, но если оно и есть, то сложность возможных комбинаций оказалась для меня запредельной (это было очень давно). Но внезапно меня осенило. Если от каждого шарика начать заливку, то она зальёт ту область, где находится шарик, какие бы сложные очертания она ни имела. А вот закрытая область без шарика залита не будет.
Как результат, шарики запускали процесс заливки (невидимый для игрока, конечно), а затем то, что оставалось незакрашенным шариками, я уже закрашивал по-настоящему.
Сейчас на проекте "Пирог" я исследую генерацию комнат и столкнулся с такой проблемой. Если два прямоугольника пересекаются вот так:
Один из прямоугольников как бы разрывается на две части и теряет свою связность. Вместо него появляются два независимых друг от друга прямоугольника. Мне нужно знать, что прямоугольник был разорван.
Опять же, данную задачу можно было решать геометрическими методами, но это всего лишь один из случаев, который я привёл для иллюстрации. Комбинации могут получаться сложнее. Поэтому я решил опять вернуться к методу закраски. Если, допустим, есть такая карта:
То я прохожу по ней, и если найду "зелёную" клетку (это в данном случае не цвет, а определённый статус), то делаю заливку с этой позиции. Вся область, связанная с этой клеткой, будет залита одним цветом. Затем я выбираю следующий цвет заливки, которым будет залита следующая область. Таким образом, все изолированные друг от друга области окажутся залиты уникальными цветами.
Зачем мне это надо, расскажу в дальнейших материалах про Пирог, а пока опишу сам алгоритм.
Побаловаться с ним можно онлайн:
https://js.do/nandakoryaaa/pyrogue-rooms-paint
А вот функция, которая выполняет заливку:
Карта хранится в виде линейного массива размером W*H, и адрес элемента с координатами (x, y) внутри массива вычисляется так:
addr = y * W + x;
При этом адрес элемента непосредственно сверху это addr - W, а адрес элемента непосредственно снизу это addr + W. Алгоритм закрашивает область по одной строке. Перед тем как начать закраску, он отходит влево от стартовой точки насколько сможет (т.е. пока цвет точки слева равен цвету стартовой точки).
Найдя начало строки, он двигается вправо, закрашивая элементы и проверяя, какие элементы находятся сверху и снизу от текущего. Если сверху есть элемент такого же цвета, его адрес (addr - W) кладётся в стек:
Аналогично для нижнего элемента.
Закончив красить строку, мы имеем некоторое количество элементов в стеке, которые ждут, чтобы их тоже покрасили. Достаём из стека последний элемент и делаем его новой стартовой точкой, в результате чего весь процесс повторяется снова. Если же в стеке не осталось элементов, то покраска окончена.
На этом пока всё, и может быть вы придумаете, где ещё можно применить заливку?