Лабораторная работа № 6. Заполнение областей

Заполнение областей

Ц е л ь р а б о т ы : освоение методов закраски областей.

Задание к работе

1. Изучить возможности графической библиотеки для получения изображений с закрашенными фигурами

2. Освоить алгоритмы закраски выпуклых, монотонных и произвольных многоугольников.

3. Освоить алгоритмы заполнения выпуклых и произвольных областей, заданных растровой разверткой границ.

4. Реализовать программно один из алгоритмов заполнения области.

Содержание отчета

1. Постановка задачи.

2. Спецификации подпрограмм.

3. Описание основных алгоритмов.

4. Тексты программ.

5. Наборы тестовых данных для построения отрезка.

6. Ответы на контрольные вопросы.

Методические указания

В большинстве приложений используется одно из существенных достоинств растровых устройств – возможность заполнения областей экрана.

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

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

Многоугольник – это фигура, ограниченная замкнутой ломаной без самопересечений. Он может быть задан последовательностью вершин А1,А2,...,Аn. Ребра определяются двумя соседними вершинами.

Ряд алгоритмов заполнения многоугольников основывается на том, что горизонтальная прямая, пересекающая ломаную, разбивает ее на чередующиеся интервалы, принадлежащие и не принадлежащие многоугольнику. Для каждого y найдем и отсортируем точки пересечения по возрастанию x. Сгруппируем их парами. Это будут отрезки, подлежащие закрашиванию (рис.6.1)

Рисунок 6.1

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

Для выпуклых многоугольников существуют более простые алгоритмы. Границы выпуклого многоугольника можно разбить на две части – левую и правую, исключив горизонтальные ребра. Каждая часть представляет собой упорядоченный список ребер.

Перемещаясь с помощью алгоритма Брезенхема одновременно по левой и правой границе, покрываем многоугольник горизонтальными отрезками, соединяя точки левой и правой границы с одинаковыми значениями y (рис.6.2).

Рисунок 6.2

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

Заполнение областей на растре

Задано разложение в растр границы области. Граница имеет цвет В. Задана точка на растре, называемая затравочной, принадлежащая области. Требуется закрасить область в цвет С. Областью называется множество пикселей, по которым существует путь по пикселям, цвет которых не равен цвету границы В. От пикселя к пикселю проходим по горизонтали или вертикали, т.е. будем рассматривать четырехсвязную область.

Простейшим алгоритмом заполнения является алгоритм ‘‘короед’’.

Procedure SimrleFill(x,y:integer;B,C:word);

begin

if (getpixel(x,y)<>B) and (getpixel(x,y)<>C) then

begin SimpleFill(x+1,y,B,C);

SimpleFill(x-1,y,B,C);

SimpleFill(x,y+1,B,C);

SimpleFill(x+1,y-1,B,C)

end;

end;

Реально используются алгоритмы построчного заполнения, основанные на том, что соседние пиксели в строке, скорее всего, одинаковы и меняются только там, где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Y_i, Y_i+1, Y_i+2 на рис.6.3). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.

Рисунок 6.3 - Построчная закраска многоугольника

Кроме того, если какие-либо ребра пересекались i-й строкой, то они, скорее всего, будут пересекаться также и строкой i+1. (строки сканирования Yi и Yi+1 на рис. 6.3). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра: Xi+1 = Xi + 1/k, где

тангенс угла наклона ребра - k = dy/dx, т. к. dy = 1, то 1/k = dx.

Смена же количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина.

Варианты заданий

Выбор алгоритма зависит от r - остатка от деления номера варианта на 4.

1. Если r=0, реализовать алгоритм закраски для выпуклого и монотонного многоугольника.

2. Если r=1, реализовать алгоритм закраски произвольного многоугольника.

3. Если r=2, реализовать алгоритм заливки с затравкой выпуклой области.

4. Если r=3, реализовать алгоритм заливки с затравкой произвольной области.

Контрольные вопросы:

1. Назовите графические примитивы для вывода закрашенных фигур.

2. Как изменить стиль заливки?

3. Как установить собственный шаблон заливки?

4. На какие классы делятся алгоритмы закраски областей?

5. Как работают алгоритмы закраски областей?

Поиск по сайту: