Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм с упорядоченным списком ребер, использующий список активных рёбер.
Подготовить данные: Используя сканирующие строки, проведенные через середины отрезков, т. е. через у + ½ определить для каждого ребра многоугольника наивысшую сканирующую строку, пересекаемую ребром.
Занести ребро многоугольника в у- группу, соответствующую этой сканирующей строке.
Сохранить в связном списке значения: начальное значение координат x точек пересечения, Dy - число сканирующих строк, пересекаемых ребром многоугольника, и ~ Dx – шаг приращения по x при переходе от одной сканирующей строки к другой.
Преобразовать эти данные в растровую форму:
Для каждой сканирующей строки проверить соответствующую у- группу на наличие новых ребер. Новые ребра добавить в список активных рёбер.
Отсортировать координаты x точек пересечения из САР в порядке возрастания; т. е. х1 предшествует x2, если х1 < х2 Выделить пары точек пересечений из отсортированного по x списка. Активировать на сканирующей строке y пикселы для целых значений x, таких, что x1 £ x + ½ £ x2. Для каждого ребра из САР уменьшить Dу на 1. Если Dу < 0, то исключить данное ребро из САР. Вычислить новое значение координат x точек пересечения xнов = xстар + Dx Перейти к следующей сканирующей строке
В алгоритме предполагается, что все данные предварительно преобразованы в представление, принятое для многоугольников. Алгоритм заполнения по рёбрам Алгоритм, использующий список ребер и флаг, является двух шаговым. Первый шаг состоит в обрисовке контура, врезультате чего на каждой сканирующей строке образуются пары ограничивающих пикселов. Второй шаг состоит в заполнениипикселов, расположенных между ограничивающими. Более точно алгоритм можно сформулировать в следующем виде:
Алгоритм со списком ребер и флагом Обрисовка контура: Используя соглашения о середине интервала между сканирующими строками для каждого ребра, пересекающего сканирующую строку, отметить самый левый пиксел, центр которого лежит справа от пересечения; т.е. x + 1/2 > xпересечения Заполнение: Для каждой сканирующей строки, пересекающей многоугольник Внутри = FALSE for x = 0 (левая граница) to x = xmax, (правая граница) if пиксел в точке x имеет граничное значение then инвертировать значение переменной Внутри
if Внутри = TRUE then присвоить пикселу в x значение цвета многоугольника Else присвоить пикселу в x значение цвета фона End if next x
В данном алгоритме каждый пиксел обрабатывается только один раз, так что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком рёбер, в результате чего, при его аппаратной реализации, он работает на один-два порядка быстрее чем алгоритм с упорядоченным списком рёбер. Алгоритмы заполнения с затравкой В обсуждавшихся выше алгоритмах заполнение происходит в порядке сканирования. Иной подход используется в алгоритмах заполнения с затравкой. В них предполагается, что известен хотя бы один пиксел из внутренней области многоугольника. Алгоритм пытается найти и закрасить все другие пикселы, принадлежащие внутренней области. Области могут быть либо внутренние, либо гранично-определенные.
Рис. 2.10. Внутренне - определённая область Рис. 2.11. Гранично-определённая область
Если область относится к внутренне - определенным, то все пикселы, принадлежащие внутренней части, имеют один и тот же цвет или интенсивность, а все пикселы, внешние по отношению к области, имеют другой цвет. Это продемонстрировано на рис. 2.10. Если область относится к гранично-определенным, то все пикселы на границе области имеют выделенное значение или цвет, как это показано на рис. 2.11. Алгоритмы, заполняющие внутренне - определенные области, называются внутренне - заполняющими, а алгоритмы для гранично-определённых областей – гранично-заполняющими. Далее будут обсуждаться гранично-заполняющие алгоритмы, однако соответствующие внутренне заполняющие алгоритмы можно получить аналогичным образом. Внутренне- или гранично-определённые области могут быть 4- или 8- связными. Если область 4-связная, то любой пиксел в области можно достичь с помощью комбинаций движений только в 4-х направлениях: налево, направо, вверх, вниз. Для 8-и связной области добавляются ещё и диагональные направления. Алгоритм заполнения 8-связной области заполнит и 4-связную, но обратное не верно. Однако в ситуации, когда требуется заполнить разными цветами две отдельные 4-связные области, использование 8-связного алгоритма даст не верный результат. Далее речь пойдёт об алгоритмах для 4-связных областей, однако их легко адаптировать и для 8-связных.
Построчный алгоритм заполнения с затравкой Используя стек, можно разработать алгоритм заполнения гранично-определенной области. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Как показывает практика, стек может быть довольно большим. Зачастую в нём содержится дублирующаяся информация. В построчном алгоритме заполнения с затравкой стек минимизируется за счёт хранения только затравочного пиксела для любого непрерывного интервала на сканирующей строке. Непрерывный интервал - это группа примыкающих друг к другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы для разработки алгоритма используем эвристический подход, однако также возможен и теоретический подход, основанный на теории графов. Данный алгоритм применим гранично-определённым 4-связным областям, которые могут быть как выпуклыми, так и не выпуклыми, а также могут содержать дыры. В области, внешней и примыкающей к нашей, не должно быть пикселов с цветом, которым область или многоугольник заполнятся. Схематично работу алгоритма можно разбить на четыре этапа.
Построчный алгоритм заполнения с затравкой Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы.
Интервал с затравочным пикселом заполняется влево и вправо от затравки вдоль сканирующей строки до тех пор пока не будет найдена граница.
В переменной Xлев и Xправ запоминаются крайний левый и крайний правый пикселы интервала
В диапазоне Xлев £ x £ Xправ проверяются строки расположенные непосредственно над в под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т. е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек.
При инициализации алгоритма в стек помешается единственный затравочный пиксел, работа завершается при опустошении стека. Ниже приводится более подробное описание алгоритма на псевдокоде.
|
||||||
Последнее изменение этой страницы: 2020-03-26; просмотров: 338; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.117.156.37 (0.011 с.) |