Заливка области с затравкой

Цель: Изучить алгоритмы заливки области с затравкой.
Понять, в чем основное отличие заливки области
от заполнения многоугольника

5.1. Заливка области с затравкой

По способу задания области делятся на два типа (рис. 5.1):

· гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселов, границы которых отличны от кодов внутренней, перекрашиваемой части области. На коды пикселов внутренней части области налагаются два условия – они должны быть отличны от кода пикселов границы и кода пиксела перекраски. Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселами с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться;

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

а) внутренне-определенная область

б) гранично-определенная область

Рис. 5.1. Деление области по способу задания

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

Заливаемая область или ее граница – некоторое связное множество пикселов. По способам доступа к соседним пикселам области делятся на 4-х и 8-ми связные. В 4-х связных областях доступ к соседним пикселам осуществляется по четырем направлениям – горизонтально влево и вправо и вертикально – вверх и вниз. В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность, мы можем, двигаясь от точки затравки, достичь и закрасить все пикселы области.

Важно отметить, что для 4-х связной прямоугольной области граница 8-ми связна (рис. 5.2 а) и, наоборот, у 8-ми связной области граница 4-х связна (рис. 5.2б). Поэтому заполнение 4-х связной области 8-ми связным алгоритмом может привести к "просачиванию" через границу и заливке пикселов в примыкающей области.

а) 4-х б) 8-ми

связанные, внутренне-определенные области

Рис. 5.2. Связанность областей

В общем, 4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно.

С использованием связности областей и стека можно построить простые алгоритмы закраски как внутренне, так и гранично-определенной области.

Простой алгоритм заливки

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

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

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

Ниже приведен итеративный алгоритм закраски 4-х связной гранично-определенной области. Логика работы алгоритма следующая:

· поместить координаты затравки в стек;

· пока стек не пуст;

· извлечь координаты пиксела из стека;

· перекрасить пиксел;

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

· если нет, то занести его координаты в стек.

На рис. 5.3 а) показан выбранный порядок перебора соседних пикселов, а на рис. 5.3 б) – соответствующий ему порядок закраски простой гранично-определенной области.

a) Порядок перебора соседних пикселов

б) Порядок заливки области

Рис. 5.3. Заливка 4-х связной области итеративным алгоритмом

Рассмотренный алгоритм легко модифицировать для работы с 8-ми связными гранично-определенными областями или же для работы с внутренне-определенными.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: