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

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

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

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

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

Последовательность работы алгоритма для гранично-опреде-ленной области следующая:

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

· координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Х _лев и Х _прав соответственно.

Анализируется строка ниже закрашиваемой в пределах от Х _лев до Х _прав и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек. То же самое проделывается для строки выше закрашиваемой.

Задание на лабораторную работу № 5
"Заливка области с затравкой "

1. Построить область с отверстиями, произвести заполнение, используя алгоритм простой затравки.

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

3. В чем суть итеративного и рекурсивного алгоритмов?

4. Что такое пространственная когерентность?

5. Сравните два алгоритма, найдите недостатки и преимущества.

6. Чем отличаются 4- и 8-связные алгоритмы (и области). Преимущества и недостатки.

Алгоритмы отсечения отрезков

Цель: Изучить алгоритмы отсечения отрезков

Отсечение – процесс выделения некоторой базы данных.

Используется:

– при выделении окна;

– при выходе изображения за границы экрана;

– для устранения ступенчатости изображения.

Отсекаемые отрезки могут быть трех классов: целиком видимые, целиком невидимые и пересекающие окно. Очевидно, что целесообразно возможно более рано, без выполнения большого объема вычислений принять решение о видимости целиком или отбрасывании. По способу выбора решения существует два основных типа алгоритмов отсечения – алгоритмы, использующие кодирование концов отрезка или всего отрезка (алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм) и FC-алгоритм (Fast Clipping-алгоритм)) и алгоритмы, использующие параметрическое представление отрезков и окна отсечения (алгоритм Кируса-Бека (Curus-Beck, CB-алгоритм) и алгоритм Лианга-Барски
(Liang-Barsky, LB-алгоритм)). Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, а алгоритмы с параметрическим представ-лением применимы для произвольного окна.