Алгоритмы заливки замкнутых областей.

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

Заливаемая область или ее граница - некоторое связное множество пикселов. По способам доступа к соседним пикселам области делятся на 4-х и 8-ми связные:

1. В 4-х связных областях доступ к соседним пикселам осуществляется по четырем направлениям - горизонтально влево и вправо и в вертикально вверх и вниз.
2. В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность мы может, двигаясь от точки затравки, достичь и закрасить все пикселы области. Важно отметить, что для 4-х связной прямоугольной области граница 8-ми связна и наоборот у 8-ми связной области граница 4-х связна. Поэтому заполнение 4-х связной области 8-ми связным алгоритмом может привести к "просачиванию" через границу и заливке пикселов в примыкающей области. В общем, 4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно.
3. Рис: Связность областей и их границ

Простой алгоритм заливки гранично-определенной 4-х связной области. Рекурсивная реализация подпрограммы заливки 4-х связной гранично-определенной области.

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

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

2. если нет, то пиксел перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пиксела.

Заливка области, заданной координатами своих вершин

1. Алгоритмы построчного заполнения, основанные на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Y_i, Y_i+1, Y_i+2 на рис. ).При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.

2. Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и строкой i+1. (строки сканирования Y_i и Y_i+1 на рис). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра: x_i+1 = x_i + 1/k

(тангенс угла наклона ребра k = dy/dx, так как dy = 1, то 1/k = dx).

3. Смена количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина.

Заливка области, заданной цветом границы (заливка с затравкой)

(для областей созданных в результате интерактивной работы)

Задается

· заливаемая (перекрашиваемая) область,

· код пиксела, которым будет выполняться заливка и

· начальная точка в области, начиная с которой начнется заливка (затравка).

По способу задания области делятся на два типа:

1. гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселов границы отличны от кодов внутренней, перекрашиваемой части области. На коды пикселы внутренней части области налагаются два условия:

o они должны быть отличны от кода пикселов границы и кода пиксела перекраски.

o Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселами с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться;

2. внутренне-определенные, нарисованные одним определенным кодом пиксела. При заливке этот код заменяется на новый код закраски.

Основное отличие заливки области с затравкой от заполнения многоугольника:

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

· В алгоритмах же заливки области с затравкой нам вначале надо прочитать пиксел, затем определить принадлежит ли он области и если принадлежит, то перекрасить.

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

Заполнение круга. Для этого можно использовать алгоритм, основанный на симметрии круга – в основном цикле вычисляются координаты точек круга только для одного октанта и сразу рисуются восемь симметрично расположенных пикселов.(Алгоритм Брезенхэма). То есть для заполнения необходимо выводить горизонтальные линии, соединяющие пары точек на контуре, расположенные симметрично относительно оси Y.

Заполнение многоугольников. Контур многоугольника, как уже было определено, определяется вершинами, которые соединены отрезками прямых. Это есть векторная форма заполнения фигуры. Основная идея наиболее распространенного алгоритма заполнения многоугольника состоит в следующем. Закрашивание происходит отрезками прямых линий. Наиболее удобно использовать горизонтали. Алгоритм представляет собой цикл, в ходе которого выполняется поиск точек сечения линии контура с соответствующими горизонталями. В алгоритме использовано свойство топологии контура фигуры, состоящее в том, что любая прямая линия пересекает любой замкнутый контур четное количество раз. При нахождении точек пересечения горизонтали с контуром необходимо принимать во внимание особые точки: горизонталь проходит через вершину, горизонталь касается вершины (вершина соответствует локальному минимуму или максимуму).