Исследование алгоритмов заливки изображений - Программирование, компьютеры и кибернетика курсовая работа
Главная
Программирование, компьютеры и кибернетика
Исследование алгоритмов заливки изображений
Алгоритмы растровой графики (построчное заполнение, сортировка методом распределенного расчета, заливка области с затравкой) и векторной графики (заливка основным цветом, изображением-узором, текстурная, градиентная). Процедура заполнения областей экрана.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
В большинстве приложений используется одно из существенных достоинств растровых устройств - возможность заполнения областей экрана.
Существует две разновидности заполнения:
· первая, связанная как с интерактивной работой, так и с программным синтезом изображения, служит для заполнения внутренней части многоугольника, заданного координатами его вершин;
· вторая, связанная в первую очередь с интерактивной работой, служит для заливки области, которая либо очерчена границей с кодом пиксела, отличающимся от кодов любых пикселов внутри области;
Простейший способ заполнения многоугольника, заданного координатами вершин, заключается в определении принадлежит ли текущий пиксел внутренней части многоугольника. Если принадлежит, то пиксел заносится.
Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел внутри, то угол будет равен 360 ? , если вне - 0 ?
Рис. 1: Определение принадлежности пиксела многоугольнику
Вычисление принадлежности должно производиться для всех пикселов экрана и так как большинство пикселов скорее всего вне многоугольников, то данный способ слишком расточителен.
Реально используются алгоритмы построчного заполнения, основанные на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Y i , Y i+1 , Y i+2 на рис. ). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.
Рис. 2: Построчная закраска многоугольника
Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и строкой i+1. (строки сканирования Y i и Y i+1 на рис. 2). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра:
(тангенс угла наклона ребра - k = dy/dx, так как dy = 1, то 1/k = dx).
Смена же количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина.
Учет когерентности строк и ребер позволяет построить для заполнения многоугольников различные высокоэффективные алгоритмы построчного сканирования. Для каждой строки сканирования рассматриваются только те ребра, которые пересекают строку. Они задаются списком активных ребер (САР). При переходе к следующей строке для пересекаемых ребер перевычисляются X-координаты пересечений. При появлении в строке сканирования вершин производится перестройка САР. Ребра, которые перестали пересекаться, удаляются из САР, а все новые ребра, пересекаемые строкой заносятся в него.
Общая схема алгоритма, динамически формирующего список активных ребер и заполняющего многоугольник снизу-вверх, следующая:
1. Подготовить служебные целочисленные массивы Y-координат вершин и номеров вершин.
2. Совместно отсортировать Y-координаты по возрастанию и массив номеров вершин для того, чтобы можно было определить исходный номер вершины.
3. Определить пределы заполнения по оси Y - Y_мin и Y_max. Стартуя с текущим значением Y_tek = Y_min, исполнять пункты 4-9 до завершения раскраски.
4. Определить число вершин, расположенных на строке Y_tek - текущей строке сканирования.
5. Если вершины есть, то для каждой из вершин дополнить список активных ребер, используя информацию о соседних вершинах. Для каждого ребра в список активных ребер заносятся:
· максимальное значение Y-координаты ребра,
· приращение X-координаты при увеличении Y на 1,
Если обнаруживаются горизонтальные ребра, то они просто закрашиваются и информация о них в список активных ребер не заносится. Если после этого обнаруживается, что список активных ребер пуст, то заполнение закончено.
6. По списку активных ребер определяется Y_след - Y-координата ближайшей вершины. (Вплоть до Y_след можно не заботиться о модификации САР а только менять X-координаты пересечений строки сканирования с активными ребрами).
o выбрать из списка активных ребер и отсортировать X-координаты пересечений активных ребер со строкой сканирования;
o определить интервалы и выполнить закраску;
o перевычислить координаты пересечений для следующей строки сканирования.
8. Проверить не достигли ли максимальной Y-координаты. Если достигли, то заливка закончена, иначе выполнить пункт .
9. Очистить список активных ребер от ребер, закончившихся на строке Y_след и перейти к пункту 4.
В Приложении 5 приведены две подпрограммы заполнения многоугольника - V_FP0 и V_FP1. Первая реализует данный (простейший) алгоритм. Эта программа вполне работоспособна, но генерирует двух и трехкратное занесение части пикселов. Это мало приемлемо для устройств вывода типа матричных или струйных принтеров.
В отличие от V_FP0, в программе V_FP1 используется более сложный алгоритм формирования списка активных ребер, обеспечивающий практически полное отсутствие дублирований (рис.).
Рис. 3: Сравнение алгоритмов заполнения многоугольника
Понятно, что одна из важнейших работ в алгоритме построчного сканирования - сортировка. В связи с заведомо ограниченной разрешающей способностью растровых дисплеев (не более 2048) иногда целесообразно использовать чрезвычайно эффективный алгоритм сортировки методом распределяющего подсчета.
Для рассмотрения алгоритма предположим, что надо отсортировать числа, заданные в массиве с именем «Исходный_массив»; количество сортируемых чисел задается скаляром «Кол-во_чисел»; сортируемые числа J удовлетворяют условию:
Для сортировки потребуются описания:
int Max_число; /* Верхняя граница значений */
int *Повтор; /* Длина этого массива = Max_число */
int Кол_чисел; /* Кол-во сортируемых чисел */
int *Исходный_массив; /* Длина этого массива >= Кол_чисел */
int *Результат; /* Длина этого массива >= Кол_чисел */
int ii,jj, kk; /* Рабочие переменные */
1. Обнуляется служебный массив для подсчета числа повторений исходных кодов.
2. for (ii=0; iiИсследование алгоритмов заливки изображений курсовая работа. Программирование, компьютеры и кибернетика.
Дипломная работа по теме Проектирование рациональной организации труда в производственном подразделении предприятия
Реферат: Поняття соціальної роботи
Реферат: Хоккайдо
Отзыв Характеристика Педагогической Практики
Реферат На Тему Инфекционный Мастит
Дипломная работа по теме Расчет ремонтной базы АТП
Реферат по теме Человечество и окружающая среда
Курсовая работа по теме Уголовно-правовая охрана избирательных прав граждан
Статья: Закономерности групповой эффективности
Реферат: Центральный банк и его функции
Лабораторная Работа По Биологии 11
Курсовая работа: Особенности электроснабжения помещений для содержания животных
Курсовая работа: Виды и методы исследований в практике связей с общественностью. Скачать бесплатно и без регистрации
Курсовая работа: Анализ опыта создания и деятельности акционерного общества ЗАО ТРК "Фотон"
Курсовая Работа На Тему Наследственность И Изменчивость
Реферат: Философия Костанеды
Spotlight 6 Module 3 Check Контрольная Работа
Иммунные Расстройства При Психоневрологических Заболеваниях Реферат
Реферат: Генезис понятия собственности
Сочинение На Тему Чему Учат Произведения Пушкина
Анальгезия и анестезия при родоразрешении через естественные родовые пути - Медицина реферат
Компаративні особливості просодичного оформлення англомовного та російськомовного офіційно-ділового дискурсу - Иностранные языки и языкознание статья
Антропологические методы оценки волос - Биология и естествознание реферат