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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двумерный алгоритм Коэна-Сазерленда

Вся область экрана делится на 9 частей (рис. 6.1). Для определения, к какой из девяти областей принадлежит конец отрезка, вводится 4-х битовый код; биты считаются справа и единица ставится в бит, если:

- 1 бит – точка левее окна;

- 2 бит – точка правее окна;

- 3 бит – точка ниже окна;

- 4 бит – точка выше окна.

Центральная область имеет код – 0000.

Рис. 6.1. Задание кодов областей для алгоритма Коэна-Сазерленда

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

Двумерный FC-алгоритм

В данном алгоритме кодируется весь отрезок целиком. Схема кодирования близка к используемой в алгоритме Коэна-Сазерленда. Все пространство экрана разбивается на 9 частей и они кодируются цифрами от 1 до 9 (рис. 6.2). Отрезок кодируется следующим образом:

LineCode(V₀V₁) = Code(V₀)*16 + Code(V₁),

где Code(V₁) – код конечной точки;

Code(V₀) – код начальной точки,

*16 – означает сдвиг влево на 4 разряда,

LineCode(V₀V₁) – код отрезка.

Рис. 6.2. Задние кодов областей для FC-алгоритма

Так как каждый код может принимать только девять значений, то имеется 81 возможный вариант расположения отрезка и требуется свой набор вычислений для определения отсечения отрезка за минимальное время. Однако, имеется всего 8 основных случаев отсечения, остальные симметричны им. Иллюстрации для случаев 1-7 приведены на рис. 6.3, а для случая 8 – на рис. 6.4. Итак:

Случай 1 – начальная и конечная точки отрезка находятся в области 4 (отрезок LA, LineCode(V₀V₁) = 44). Отрезок не пересекает видимую область и отбрасывается.

Случай 2 – начальная точка находится в области 4, конечная – в области 1 (отрезок LB, LineCode(V₀V₁) = 41). Отрезок не пересекает видимую область и отбрасывается.

Случай 3 – начальная точка находится в области 4, конечная – в области 2 (отрезки LC и LD, LineCode(V₀V₁) = 42). Отрезок явно пересекает X_лев. Вычисляем точку пересечения отрезка с левым ребром – (X_лев, Y_п). Eсли Y_п > Y_верхн, то

Рис. 6.3 Варианты расположения отрезка для
неугловых областей (FC-алгоритм)

Рис. 6.4. Варианты расположения отрезка для
угловых областей (FC-алгоритм)

это отрезок LC, он не пересекает видимую область и отбрасывается. Иначе, это отрезок LD, пересекающий видимую область и необходимо вычислить точку пересечения отрезка с Y_верхн и изобразить видимую часть отрезка.

Случай 4 – начальная точка находится в области 4, конечная – в области 3 (отрезки LE, LF и LG, LineCode(V₀V₁) = 43). Вычисляем точку пересечения с левым ребром – (X_лев, Y_п1). Eсли Y_п1 > Y_верхн, то это отрезок LE, он не пересекает видимую область и отбрасывается, иначе это отрезки LF или LG. Вычисляем точку пересечения с правым ребром (X_прав, Y_п2). Eсли Y_п2 > Y_верхн, то это отрезок LF и необходимо вычислить точку пересечения с верхним ребром и изобразить видимую часть отрезка. Иначе это отрезок LG, точки пересечения с левым и правым ребрами известны, следовательно, изображаем видимую часть отрезка.

Случай 5 – начальная точка находится в области 4, конечная – в области 6 (отрезок LH, LineCode(V₀V₁) = 46). Вычисляем точки пересечения с левым и правым ребрами и изображаем видимую часть отрезка.

Случай 6 – начальная точка находится в области 4, конечная – в области 5 (отрезок LI, LineCode(V₀V₁) = 45). Вычисляем точку пересечения с левым ребром и изображаем видимую часть отрезка.

Случай 7 – начальная точка находится в области 5, конечная – в области 5 (отрезок JK, LineCode(V₀V₁) = 55). Отрезок полностью видим, изображаем его.

Случай 8 – начальная точка находится в области 7, конечная – в области 3 (отрезки RW, SX, SY, TX,TY,UZ LineCode(V₀V₁) = 73). Вычисляем точку пересечения с левым ребром – (X_лев, Y_п1). Eсли Y_п1 > Y_верхн, то это отрезок RW, он не пересекает видимую область и отбрасывается. Вычисляем точку пересечения с правым ребром ребром – (X_прав, Y_п2). Eсли Y_п2 < Y_нижн, то это отрезок UZ, он не пересекает видимую область и отбрасывается. Если Y_п1 > Y_нижн, то начальная точка S и если Y_п2 < Y_вехн, то это отрезок SY и мы изображаем его видимую часть, иначе, это отрезок SX, вычисляем точку пересечения с верхней стороной и также изображаем видимую часть отрезка. Оставшийся вариант – начальная точка T и если Y_п2 < Y_вехн, то это отрезок TY и мы изображаем его видимую часть, иначе, это отрезок TX, вычисляем точку пересечения с верхней стороной и также изображаем видимую часть отрезка.

Алгоритм Кируса-Бека

Алгоритм Кируса-Бека относится к классу алгоритмов с параметрическим представлением отрезка и окна отсечения. При создании надежного алгоритма отсечения необходимо иметь хороший метод определения местоположения относительно окна точки, принадлежащей отрезку, – внутри, на границе или вне окна. Для этого в алгоритме Кируса-Бека используется вектор нормали.

Возьмем выпуклую двумерную область R (рис. 6.5) – она должна быть выпуклым многоугольником. Внутренняя нормаль в точке a, лежащей на границе R, удовлетворяет условию:

n_вн*(b– a) ³ 0,

где b – любая точка, лежащая на границе R.

Рис. 6.5. Определение местоположения точки относительно
окна отсечения в алгоритме Кируса-Бека

Так как скалярное произведение двух векторов равно:

V₁*V₂ = çV₁ç*çV₂ç*cos(Q),

где Q - меньший из двух углов, образованных V₁ и V₂. Причем, если Q = p/2, то V₁*V₂ = 0 и вектора V₁и V₂ перпендикулярны. Угол Q между n_вн и любым вектором между точками a и b всегда принадлежит интервалу –p/2 £ Q£ p/2 и, следовательно, cos(Q) всегда ³ 0 и скалярное произведение n_вн*(b – a) неотрицательно (для внешней (наружной) нормали скалярное произведение n_нар*(b – a) всегда неположительно).

Параметрическое представление отрезка имеет вид:

P(t) = P₁ + (P₂ – P₁)*t; 0 £ t £ 1.

Если f – граничная точка выпуклой области R, а n – внутренняя нормаль к одной из ограничивающих эту область плоскостей, то для любой конкретной величины t (т.е. для любой точки отрезка P₁P₂) из условия n*(P(t) – f) < 0 следует, что вектор (P(t) – f) направлен вовне области R, из условия n*(P(t) – f) = 0 следует, что вектор (P(t) – f) принадлежит плоскости, которая проходит через f, и перпендикулярен нормали, из условия n*(P(t) – f) > 0 следует, что вектор
(P(t) – f) направлен внутрь области R (рис. 6.6).

Из всех условий взятых вместе следует, что бесконечная прямая пересекает замкнутую область (выпуклую двумерную) ровно в двух точках и уравнение n*(P(t) – f) = 0 имеет только одно решение и точка P(t) будет точкой пересечения отрезка с граничной плоскостью.

Из всего вышесказанного и вытекает алгоритм Кируса-Бека.

Параметрическое описание отрезка (как уже отмечалось выше) имеет вид:

P(t) = P₁ + (P₂ – P₁)*t; 0 £ t £ 1.

Рис. 6.6. Исходные данные для алгоритма Кируса-Бека

Скалярное произведение внутренней нормали на вектор, начинающийся в произвольной точке отрезка и заканчивающийся в другой точке, лежащей на той же границе окна (n_i*(P(t) – f_i ); i = 1,2…) будет положительным, равным нулю или отрицательным в зависимости от того, будет ли избранная точка отрезка лежать с внутренней стороны границы, на самой границе или с ее внешней стороны. Это справедливо для любого ребра. Подставим P(t) для нахождения пересечения:

n_i*[P₁ + (P₂ – P₁)*t – f_i] = 0

Или в другой форме:

n_i*[P₁ –f_i] +n_i*[P₂ – P₁]*t = 0

Вектор (P₂ – P₁) – определяет ориентацию отрезка, а вектор (P₁ – f_i) пропорционален расстоянию от первого конца отрезка до избранной граничной точки. Обозначим D = (P₂ – P₁) – директриса или ориентация отрезка, а
w_i = (P₁ – f_i) – весовой множитель, тогда:

t*(n_i*D) + w_i*n_i = 0
t = –(w_i*n_i) / (n_i*D); D ¹ 0; i = 1, 2, 3, …

Равенство D нулю означает, что P₂ = P₁, т.е. вырождение отрезка в точку и при этом если w_i*n_i < 0, то точка вне окна отсечения, если w_i*n_i = 0, то точка находится на границе окна отсечения, если w_i*n_i > 0, то точка внутри окна отсечения. Вычисляем t, если значение лежит за пределами интервала 0 £ t £ 1, то можно его проигнорировать. Может получиться более двух значений t в допустимом интервале. Эти значения следует разбить на две группы: нижнюю и верхнюю в зависимости от того, к началу или к концу отрезка будет ближе вычисленная точка. Необходимо найти наибольшую из нижней группы и наименьшую из верхней группы. При этом если n_i*D > 0, то найденное значение t рассматривается в качестве возможного нижнего предела, иначе – верхнего. Блок – схема алгоритма приведена на рис. 6.7.

Рис. 6.7. Алгоритм Кируса-Бека

Для успешной реализации алгоритма Кируса-Бека необходимо знать, выпуклый многоугольник или нет, и определить уравнение внутренней нормали.

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