Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Используя сканирующие строки, проведенные через середины отрезков, т. е. через у + Ѕ определить для каждого ребра многоугольника наивысшую сканирующую строку, пересекаемую ребром.

Занести ребро многоугольника в у- группу, соответствующую этой сканирующей строке.

Сохранить в связном списке значения: начальное значение координат 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. Построчный алгоритм заполнения с затравкой

Используя стек, можно разработать алгоритм заполнения гранично- определенной области. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Как показывает практика, стек может быть довольно большим. Зачастую в нём содержится дублирующаяся информация. В построчном алгоритме заполнения с затравкой стек минимизируется за счёт хранения только затравочного пиксела для любого непрерывного интервала на сканирующей строке. Непрерывный интервал - это группа примыкающих друг к другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы для разработки алгоритма используем эвристический подход, однако также возможен и теоретический подход, основанный на теории графов.

Рекомендуем скачать другие рефераты по теме: предмет культурологии, реферат на тему организация.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата