Алгоритм закрашивания

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

Алгоритмы двумерной растровой графики: закрашивание

Рассмотрим алгоритмы закрашивания произвольного контура, который уже нарисован в растре. Сначала находится пиксель внутри контура фигуры. Цвет этого пикселя изменяем на нужный цвет заполнения. Потом проводится анализ цвета всех соседних пикселей. Если цвет некоторого соседнего пикселя не равен цвету границы контура или цвету заполнения, то цвет этого пикселя изменяется на цвет заполнения.

Простое рекурсивное заполнение.

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

Procedure PixelFill (x, y, BColor, Color : Integer);

{x, y – координаты затравочной точки, BColor – цвет границы,

Color – цвет заполнения}

Var C : Integer;

Begin

C:=GetPixel (x,y) {анализируем текущий цвет пикселя}

if (C<>BColor) and (C<>Color) then

Begin

PutPixel (x, y, Color);

PixelFill (x+1, y, BColor, Color);

PixelFill (x, y+1, BColor, Color);

PixelFill (x-1, y, BColor, Color);

PixelFill (x, y-1, BColor, Color);

End;

End;

Этот алгоритм не оптимизирован относительно использования стековой памяти и является одним из самых медленных алгоритмов закрашивания (в среднем только один из четырёх вызовов используется для закрашивания). Алгоритм не может заполнить области, ограниченные цветом заполнения. Можно построить подобный алгоритм и без рекурсии, если вместо стека использовать массивы.

Алгоритм закрашивания линиями.

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

1.Имеется затравочная точка с координатами (x_st, y_st) и начальное направление действия рекурсивных вызовов dir=1. Параметры левой и правой границы вначале совпадают с координатой затравочной точки: x_PL = x_st, x_PR = x_st. Вызывается процедура LineFill, в которой: 2. Находятся x_L и x_R – левая и правая границы, между которыми проводится текущая горизонтальная линия. 3.Делается приращение у=у+dir и, между x_L и x_R, анализируется цвет пикселей над линией. Если он не совпадает с цветом заполнения, процедура LineFill вызывается рекурсивно с dir = 1 и x_PL = x_L, x_LR = x_R. 4.Делается приращение y=y–dir и, начиная от x_L до предыдущего значения x_PL анализируется цвет пикселей под линией. Если цвет пикселя отличается от цвета заполнения, процедура вызывается рекурсивно с dir = –1 и x_PL = x_L, x_PR = x_R. 5.Продолжая по той же горизонтали от предыдущего x_PR до x_R анализируется цвет под линией. Если цвет какого-либо пикселя отличается от цвета заполнения, процедура вызывается рекурсивно с dir = –1 и x_PL = x_L, x_PR = x_R. Ниже приведен пример реализации этого алгоритма на языке С++:

void LineFill (int x, int y, int dir, int xPL, int xPR)

{

int xL=x; xR=x;

int color;

// в этой переменной будет храниться цвет пикселя

// УСТАНАВЛИВАЕМ ТЕКУЩИЕ ГРАНИЦЫ xL И xR

do

color = GetPixel (--xL,y);

// xL=xL-1 помещается в вызов функции

while (color != bcolor); // bcolor – цвет границы

do

color = GetPixel (++xR,y);

while (color !=bcolor);

xL++; xR--;

Line (xL,y, xR,y, Mycolor);

//это может быть любая функция рисования линии

// АНАЛИЗИРУЕМ ПИКСЕЛИ НАД ЛИНИЕЙ

for (x=xL; x<=xR; x++) {

color = GetPixel (x, y+dir);

if (color !=bcolor)

x = LineFill (x, y+dir, dir, xL, xR);

}

// АНАЛИЗИРУЕМ ПИКСЕЛИ ПОД ЛИНИЕЙ СЛЕВА

for (x=xL; x<=xPL; x++) {

color = GetPixel (x, y-dir);

if (color !=bcolor)

x = LineFill (x, y–dir, –dir, xL, xR);

}

// АНАЛИЗИРУЕМ ПИКСЕЛИ ПОД ЛИНИЕЙ СПРАВА

for (x=xPR; x<=xR; x++) {

color = GetPixel (x, y-dir);

if (color !=bcolor)

x = LineFill (x, y–dir, –dir, xL, xR);

}

}

В программах функция LineFill вызывается следующим образом:

LineFill (xst, yst, 1, xst, xst);

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

27. Алгоритм отсечения отрезка Сазерленда-Коэна.

Алгоритм Коэна — Сазерленда (англ. Cohen-Sutherland) — алгоритм отсечения отрезков, то есть алгоритм, позволяющий определить часть отрезка, которая пересекает прямоугольник. Был разработан Дэном Коэном и Айвеном Сазерлендом в Гарварде в 1966—1968 гг., и опубликован на конференции AFIPS в 1968.^[1][2]

Описание алгоритма

Алгоритм разделяет плоскость на 9 частей прямыми, которые образуют стороны прямоугольника. Каждой из 9 частей присваивается четырёхбитный код. Биты (от младшего до старшего) значат «левее», «правее», «ниже», «выше». Иными словами, у тех трёх частей плоскости, которые слева от прямоугольника, младший бит равен 1, и так далее.

Алгоритм определяет код конечных точек отрезка. Если оба кода равны нулю, то отрезок полностью находится в прямоугольнике. Если битовое И кодов не равно нулю, то отрезок не пересекает прямоугольник (т.к. это значит, что обе конечные точки отрезка находятся с одной стороны прямоугольника). В прочих случаях, алгоритм выбирает конечную точку, находящуюся вне прямоугольника, находит ближайшую к ней точку пересечения отрезка с одной из линий, образующей стороны прямоугольника, и использует эту точку пересечения как новую конечную точку отрезка. Укороченный отрезок снова пропускается через алгоритм.

Реализация алгоритма для трёхмерной модели идентична двумерной реализации, за исключением того, что вместо четырёхразрядного кода применяется шестиразрядный (дополнительные два бита глубины).

28. Алгоритм разбиения средней точкой.