Алгоритмы растровой графики: алгоритмы заливки замкнутых фигур с границей заданного цвета, заливка многоугольников.

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

Важным понятием для растровой сетки является связность - возможность соединения двух пикселов растровой линией, т. e. последовательным набором пикселов. Возникает вопрос, когда пикселы (x ₁ ,y ₁ ) и (х₂,у₂) можно считать соседними.

4-связность: пикселы считаются соседними, если либо их x-координаты, либо их у-координаты отличаются на единицу:|x1-x2|+|y1-y2|

8-связность: пикселы считаются соседними, если их координаты x и y отличаются не более чем на единицу:|x1-x2|

1; |y1-y2|

Понятие 4-связности является более сильным: любые два 4-связных пиксела являются и 8-связными, но не наоборот. Алгоритм закраски многоуг.

Под многоугольником далее будем понимать фигуру, ограниченную на плоскости простой (непересекающейся) замкнутой ломаной. Сама ломаная задается координатами вершин Ai(xi,yi), i=1..n. Задача "закраски" многоуг. заключается в инициализации всех его внутр. точек. Н аиболее простой, но и наиболее медленный алгоритм, решающий эту задачу состоит в том, чтобы проверить все точки плоскости на принадлежность многоуг-ку. Несколько ускорить этот алгоритм можно, если вместо проверки всех точек пл-ти проверять только точки минимального квадрата заключающего многоуг-к. Е ще один вариант решения задачи, это алгоритм сканирования строк. П оследовательно проходим все горизонт. линии пл-ти, и находим отрезки на прямой, внутренние для многоуг-ка. Для данного алгоритма достаточно искать только точки пересечения сканирующей линии с ребрами многоуг-ка. Для оптимизации алгоритма можно упорядочить ребра в порядке возрастания наибольшей из ординат концов. При перемещении сканирующей прямой сверху вниз проверке на пересечение подвергаются лишь те ребра, у которых значение макс. ординаты больше ординаты сканирующей прямой. Такой алгоритм пригоден для заполнения произвол. многоуг-ков. Но если мног-к выпуклый, то алгоритм можно упростить. Границу выпуклого многоуг-ка можно разбить на 2 ломаные "левую" и "правую" и, возможно, 2 ребра "верхнее" и "нижнее" так что каждая из боковых ломаных имеет ровно 1 пересечение с каждой сканирующей прямой. Далее, используя алгоритм Брезенхейма и одновременно генерируя растровое представление для ребер левой и правой части ломаных границ, получаем левый и правый пиксели границы многоуг-ка на каждой сканирующей горизонтальной прямой. Последовательно заполняя интервалы между этими пикселами для каждого значения ординаты от верхней строки развертки до нижней, получим растровое представление многоуг-ка. Алгоритм закраски произвол. области с затравкой.

Рассмотрим класс алгоритмов "закраски"-алгоритмы заполнения области с затравкой. В этих алгоритмах предполагается, что граница области задана на растр. пл-ти и указана одна из внутр. точек области, которая называется затравочной. Треб-ся заполнить определенным цветом связную компоненту области, содержащую затравочную точку. Данному классу алгоритмов можно сопоставить физическую интерпретацию, представить, что в затравочной точке помещен источник, заливающий всю область опред. цветом. Поэтому часто такие алгоритмы называют алгоритмами заливки. Допустим нам надо "закрасить" цветом IColor область, граница, которой имеет цвет BColor, и нам задана точка с координатами (x0,y0) в качестве затравочной. 1 Поместим затравочную точку на стек. 2 Извлекаем координаты точки с вершины стека в переменные (x,y)

3 Если Screen[x,y]=IColor, то Screen[x,y]=IColor 4 Для всех соседних точек (xg,yg) повторить пункт 5 5 Если Screen[xg,yg]<>BColor и Screen[xg,yg]<>IColor, то поместить точку (xg,yg) на стек. 6 Если стек не пуст, то переходим к пункту 2.

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

2 Извлекаем координаты точки с вершины стека в переменные (x,y)

3 Заполняем максимально возможный интервал, в котором находится точка, вправо и влево вплоть до достижения граничных точек. 4 Запоминаем крайнюю левую xl и крайнюю правую xr абсциссы заполненного интервала.

5 В соседних строках над и под интервалом (xl,xr) находим незаполненные к настоящему моменту внутренние точки области, которые объединены в интервалы, а в правый конец каждого такого интервала помещаем на стек.

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

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