САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ОТЧЕТ

ПО КУРСУ

“Диалоговые системы и машинная графика”

ЗАДАНИЕ № 4

Преподаватель: Курочкин М.А.

Студент: Дмитроченко А.А.

Группа 4086

2001г.

1. Постановка задачи:

Необходимо реализовать алгоритм заливки гранично-заданной области с затравкой.

2. Модель

Задается заливаемая (перекрашиваемая) область, код пиксела, которым будет выполняться заливка и начальная точка в области, начиная с которой начнется заливка.

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

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

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

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

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

Важно отметить, что для 4-х связной прямоугольной области граница 8-ми связна и, наоборот, у 8-ми связной области граница 4-х связна.

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

Построчный алгоритм заливки с затравкой:

Использует пространственную когерентность:

- пиксели в строке меняются только на границах;

- при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксель.

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