Алгоритм заполнения сплошных областей со списком ребер и флагом

Процесс реализации алгоритма со списком ребер и флагом состоит из следующих этапов:

1. Обрисовка контура. Строки сканирования проходят через центр строк пикселей, то есть через середину интервала y+1/2. После определения пересечений вычисляется самый левый пиксель, центр которого лежит справа от точки пересечения; т.е. x+1/2>хпересечения.

2. Заполнение области. Для каждой строки сканирования, имеющей точки пересечения с многоугольником, реализуется алгоритм, изображенный на рис. 2. Иллюстрация работы алгоритма заполнения по ребрам и флагу приведена на рис. 3.

Пример. Рассмотрим многоугольник с вершинами с точках Р1 (1,1), Р2(8,1), Р3(8,6), Р4(5,3) и Р5(1,7).

При реализации алгоритма сначала обрисовывается контур, результат этого шага показан на рис. 3а. Активированы пиксели в точках (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,6), (3,5), (4,4), (5,3), (6,3), (7,4), (8,4), (8,3), (8,2), (8,1).

Затем многоугольник заполняется. Рассмотрим, например, строку сканирования 3 на рис. 3,b. Для обрисовки контура на этой строке активированы пиксели при х=1, 5, 6 и 8. Применение алгоритма заполнения дает следующие результаты:

Сначала Flag=FALSE

Для х=0 пиксель - не граничный и Flag=FALSE, поэтому никаких действий не предпринимается.

Для х=1 пиксель - граничный, поэтому переменная Flag инвертируется и принимает значение TRUE. Поскольку Flag=TRUE, пикселю присваивается цвет или интенсивность многоугольника.

Для х=2,3,4. Пиксель - не граничный и Flag=TRUE, поэтому пикселю присваивается цвет многоугольника.

Для х=5 Пиксель - граничный, поэтому Flag инвертируется. Flag=FALSE, значит пикселю присваивается фоновый цвет.

Для х=6 Пиксель - граничный, поэтому Flag инвертируется. Flag= TRUE, значит пикселю присваивается цвет многоугольника.

Для х=7 Пиксель - не граничный и Flag= TRUE, поэтому пикселю присваивается цвет многоугольника.

Для х=8 Пиксель - граничный, поэтому Flag инвертируется. Flag=FALSE, значит пикселю присваивается фоновый цвет.

Результат представлен на рис. 3,с.

Рис. 2. Алгоритм заполнения области со списком ребер и флагом

Рис. 3. Пример работы алгоритма заполнения по ребрам и флагу

Дата добавления: 2017-01-13