Дополнительная трудность возникает при пересечении сканирующей строки и многоугольника точно по вершине, как это показано на рис. 2.9. При использовании соглашения о середине интервала между сканирующими строками получаем, что строка у = 3.5 пересечет многоугольник в 2, 2 и 8, т. е. получится нечетное количество пересечений. Следовательно, разбиение пикселов на пары даст неверный результат, т. е. пикселы (0,3), (1,3) и от (3,3) до (7,3) будут фоновыми, а пикселы (2,3), (8,3), (9,3) окрасятся в цвет многоугольника. Если учитывать только одну точку пересечения с вершиной. Тогда для строки у = 3.5 получим правильный результат. Однако результат применения метода к строке у = 1.5, имеющей два пересечения в (5,1), показывает, что метод неверен. Для этой строки именно разбиение на пары даст верный результат, т. е. окрашен будет только пиксел (5,1). Если же учитывать в вершине только одно пересечение, то пикселы от (0,1) до (4,1) будут фоновыми, а пикселы от (5,1) до (9,1) будут окрашены в цвет многоугольника.
Правильный результат можно получить, учитывая точку пересечения в вершине два реза, если она является точкой локального минимума или максимума и учитывая один раз в противном случае. Определить локальный максимум или минимум многоугольника в рассматриваемой вершине можно с помощью проверки концевых точек двух ребер. Если у обоих рёбер у больше, чем у вершины, значит, вершина является точкой локального минимума. Если меньше, значит, вершина - точка локального максимума. Если одна больше, а другая меньше, следовательно, вершина не является ни точкой локального минимума, ни точкой локального максимума. На рис.2.10 точка Р1 - локальный минимум, Р3 - локальный максимум, а Р2, Р4 - ни то ни другое. Следовательно, в точках Р1 и Р3 учитываются два пересечения со сканирующими строками, а в Р2 и Р4 - одно.
7. Алгоритм с упорядоченным списком рёбер
Используя описанные выше методы, можно разработать эффективные алгоритмы растровой развертки сплошных областей, называемые алгоритмами с упорядоченным списком ребер. Эффективность этих алгоритмов зависит от эффективности сортировки. Приведём очень простой алгоритм.
Алгоритм с упорядоченным списком ребер, использующий список активных рёбер.
Подготовить данные:
Используя сканирующие строки, проведенные через середины отрезков, т. е. через у + Ѕ определить для каждого ребра многоугольника наивысшую сканирующую строку, пересекаемую ребром.
Занести ребро многоугольника в у- группу, соответствующую этой сканирующей строке.
Сохранить в связном списке значения: начальное значение координат x точек пересечения, (y - число сканирующих строк, пересекаемых ребром многоугольника, и ~ (x – шаг приращения по x при переходе от одной сканирующей строки к другой.
Преобразовать эти данные в растровую форму:
Для каждой сканирующей строки проверить соответствующую у- группу на наличие новых ребер. Новые ребра добавить в список активных рёбер.
Отсортировать координаты x точек пересечения из САР в порядке возрастания; т. е. х1 предшествует x2, если х1 < х2
Выделить пары точек пересечений из отсортированного по x списка. Активировать на сканирующей строке y пикселы для целых значений x, таких, что x1 ( x + Ѕ ( x2. Для каждого ребра из САР уменьшить (у на 1. Если (у < 0, то исключить данное ребро из САР.
Вычислить новое значение координат x точек пересечения xнов = xстар +
(x
Перейти к следующей сканирующей строке
В алгоритме предполагается, что все данные предварительно преобразованы в представление, принятое для многоугольников.
8. Алгоритм заполнения по рёбрам
Алгоритм, использующий список ребер и флаг, является двух шаговым. Первый шаг состоит в обрисовке контура, в результате чего на каждой сканирующей строке образуются пары ограничивающих пикселов. Второй шаг состоит в заполнении пикселов, расположенных между ограничивающими. Более точно алгоритм можно сформулировать в следующем виде:
Алгоритм со списком ребер и флагом
Обрисовка контура:
Используя соглашения о середине интервала между сканирующими строками для каждого ребра, пересекающего сканирующую строку, отметить самый левый пиксел, центр которого лежит справа от пересечения; т.е. x + 1/2 > xпересечения
Заполнение:
Для каждой сканирующей строки, пересекающей многоугольник
Внутри = FALSE for x = 0 (левая граница) to x = xmax, (правая граница) if пиксел в точке x имеет граничное значение then инвертировать значение переменной Внутри if Внутри = TRUE then присвоить пикселу в x значение цвета многоугольника else присвоить пикселу в x значение цвета фона end if next x
В данном алгоритме каждый пиксел обрабатывается только один раз, так что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком рёбер, в результате чего, при его аппаратной реализации, он работает на один-два порядка быстрее чем алгоритм с упорядоченным списком рёбер.
9. Алгоритмы заполнения с затравкой
В обсуждавшихся выше алгоритмах заполнение происходит в порядке сканирования. Иной подход используется в алгоритмах заполнения с затравкой. В них предполагается, что известен хотя бы один пиксел из внутренней области многоугольника. Алгоритм пытается найти и закрасить все другие пикселы, принадлежащие внутренней области. Области могут быть либо внутренние, либо гранично-определенные. Если область относится к внутренне - определенным, то все пикселы, принадлежащие внутренней части, имеют один и тот же цвет или интенсивность, а все пикселы, внешние по отношению к области, имеют другой цвет. Это продемонстрировано на рис. 2.10. Если область относится к гранично-определенным, то все пикселы на границе области имеют выделенное значение или цвет, как это показано на рис. 2.11. Алгоритмы, заполняющие внутренне - определенные области, называются внутренне - заполняющими, а алгоритмы для гранично-определённых областей – гранично-заполняющими. Далее будут обсуждаться гранично-заполняющие алгоритмы, однако соответствующие внутренне заполняющие алгоритмы можно получить аналогичным образом.
Внутренне- или гранично-определённые области могут быть 4- или 8- связными. Если область 4-связная, то любой пиксел в области можно достичь с помощью комбинаций движений только в 4-х направлениях: налево, направо, вверх, вниз. Для 8-и связной области добавляются ещё и диагональные направления. Алгоритм заполнения 8-связной области заполнит и 4-связную, но обратное не верно. Однако в ситуации, когда требуется заполнить разными цветами две отдельные 4-связные области, использование 8-связного алгоритма даст не верный результат. Далее речь пойдёт об алгоритмах для 4-связных областей, однако их легко адаптировать и для 8-связных.
10. Построчный алгоритм заполнения с затравкой
Используя стек, можно разработать алгоритм заполнения гранично- определенной области. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Как показывает практика, стек может быть довольно большим. Зачастую в нём содержится дублирующаяся информация. В построчном алгоритме заполнения с затравкой стек минимизируется за счёт хранения только затравочного пиксела для любого непрерывного интервала на сканирующей строке. Непрерывный интервал - это группа примыкающих друг к другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы для разработки алгоритма используем эвристический подход, однако также возможен и теоретический подход, основанный на теории графов.
Данный алгоритм применим гранично-определённым 4-связным областям, которые могут быть как выпуклыми, так и не выпуклыми, а также могут содержать дыры. В области, внешней и примыкающей к нашей, не должно быть пикселов с цветом, которым область или многоугольник заполнятся. Схематично работу алгоритма можно разбить на четыре этапа.
Построчный алгоритм заполнения с затравкой
Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы.
Интервал с затравочным пикселом заполняется влево и вправо от затравки вдоль сканирующей строки до тех пор пока не будет найдена граница.
В переменной Xлев и Xправ запоминаются крайний левый и крайний правый пикселы интервала
В диапазоне Xлев ( x ( Xправ проверяются строки расположенные непосредственно над в под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т. е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек.
При инициализации алгоритма в стек помешается единственный затравочный пиксел, работа завершается при опустошении стека. Ниже приводится более подробное описание алгоритма на псевдокоде.
Затравка ( x, y ) выдаёт затравочный пиксел Pop - процедура, которая извлекает пиксел из стека Push - процедура, которая помещает пиксел в стек
инициируем стек Push Затравка ( x, y ) While ( стек не пуст )
Извлекаем пиксел из стека и присваиваем ему новое значение Pop Пиксел ( x, y )
Пиксел ( x, y ) = Нов_значение сохраняем x- координату затравочного пиксела
Врем_х = x заполняем интервал справа от затравки x = x +1 while Пиксел ( x, y ) ( Гран_значение
Пиксел ( x, y ) = Нов_значение x = x +1 end while сохраняем крайний справа пиксел
Xправ = x (1 восстанавливаем x- координату затравки x = Врем_х заполняем интервал слева от затравки x = x (1 while Пиксел ( x, y ) ( Гран_значение
Пиксел ( x, y ) = Нов_значение x = x (1 end while сохраняем крайний слева пиксел
Xлев = x +1 восстанавливаем x- координату затравки x = Врем_х проверим, что строка выше не является ни границей многоугольника, ни уже полностью заполненной; если это не так, то найти затравку, начиная с левого края подинтервала сканирующей строки x = Xлев y = y +1 while x ( Xправ ищем затравку на строке выше
Флаг = 0 while ( Пиксел ( x, y ) ( Гран_значение and
Пиксел ( x, y ) ( Нов_значение and x < Xправ ) if Флаг = 0 then Флаг = 1 x = x + 1 end while помещаем в стек крайний справа пиксел if Флаг =1 then if ( x = Xправ and Пиксел ( x, y ) ( Гран_значение and Пиксел ( x, y ) ( Нов_значение ) then
Push Пиксел ( x, y ) else
Push Пиксел ( x ( 1, y ) end if
Флаг = 0 end if продолжим проверку, если интервал был прерван
Xвход = x while (( Пиксел ( x, y ) = Гран_значение or
Пиксел ( x, y ) = Нов_значение ) and x < Xправ) x = x + 1 end while удостоверимся что координата пиксела увеличена if x = Xвход then x = x + 1 end while проверим, что строка ниже не является ни границей многоугольника, ни уже полностью заполненной
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9
