Построчный алгоритм заливки с затравкой
Использует пространственную когерентность:
· пикселы в строке меняются только на границах;
· при перемещении к следующей строке размер заливаемой строки, скорее всего, или неизменен или меняется на 1 пиксел.
Таким образом, на каждый закрашиваемый фрагмент строки в стеке хранятся координаты только одного начального пиксела, что приводит к существенному уменьшению размера стека.
Последовательность работы алгоритма для гранично-опреде-ленной области следующая:
· координата затравки помещается в стек;
· координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Хлев и Хправ соответственно.
Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек. То же самое проделывается для строки выше закрашиваемой.
Задание на лабораторную работу № 5
"Заливка области с затравкой "
1. Построить область с отверстиями, произвести заполнение, используя алгоритм простой затравки.
2. Построить область с отверстиями, произвести заполнение, используя алгоритм построчной затравки.
3. В чем суть итеративного и рекурсивного алгоритмов?
4. Что такое пространственная когерентность?
5. Сравните два алгоритма, найдите недостатки и преимущества.
6. Чем отличаются 4- и 8-связные алгоритмы (и области). Преимущества и недостатки.
Алгоритмы отсечения отрезков
Цель: Изучить алгоритмы отсечения отрезков
Отсечение – процесс выделения некоторой базы данных.
Используется:
– при выделении окна;
– при выходе изображения за границы экрана;
– для устранения ступенчатости изображения.
Отсекаемые отрезки могут быть трех классов: целиком видимые, целиком невидимые и пересекающие окно. Очевидно, что целесообразно возможно более рано, без выполнения большого объема вычислений принять решение о видимости целиком или отбрасывании. По способу выбора решения существует два основных типа алгоритмов отсечения – алгоритмы, использующие кодирование концов отрезка или всего отрезка (алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм) и FC-алгоритм (Fast Clipping-алгоритм)) и алгоритмы, использующие параметрическое представление отрезков и окна отсечения (алгоритм Кируса-Бека (Curus-Beck, CB-алгоритм) и алгоритм Лианга-Барски
(Liang-Barsky, LB-алгоритм)). Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, а алгоритмы с параметрическим представ-лением применимы для произвольного окна.