Компьютерная графика. Лекция 6. Алгоритмы закрашивания

1.

КОМПЬЮТЕРНАЯ
ГРАФИКА
Лекция 6
«Алгоритмы
закрашивания»
Лектор, зав. кафедрой, к.т.н.
Степанченко Илья Викторович
Камышин 2009
Кафедра
автоматизированных
систем обработки
информации и
управления

2.

3.4. РАСТРОВЫЕ АЛГОРИТМЫ
ЗАКРАШИВАНИЯ
Под связностью понимается способ соединения
пикселей на растре.
Четырехсвязная область:
от любого пикселя можно
перейти к любому другому
пикселю движением вправо,
влево, вверх, вниз, но не по
диагонали
Восьмисвязная область:
от любого пикселя можно
перейти к любому другому
движением вправо, влево,
вверх, вниз и по диагонали
во всех направлениях

3.

3.4. РАСТРОВЫЕ АЛГОРИТМЫ
ЗАКРАШИВАНИЯ
Возможно любое соотношение связности границы
и области, кроме 8-ми связной границы и 8-ми
связной области.

4.

3.4. РАСТРОВЫЕ АЛГОРИТМЫ
ЗАКРАШИВАНИЯ
Внутреннеопределенная область: все пиксели
внутри имеют одинаковый атрибут, пиксели на
границе могут иметь разные атрибуты, но
обязательно не совпадающие с атрибутом
области.

5.

3.4. РАСТРОВЫЕ АЛГОРИТМЫ
ЗАКРАШИВАНИЯ
Гранично-определенная область: все пиксели
границы имеют одинаковый атрибут; область
внутри границы может содержать пиксели с
разными атрибутами, но обязательно не
совпадающими с атрибутом границы.

6.

3.4.1. АЛГОРИТМ ПИКСЕЛЬНОГО
ЗАКРАШИВАНИЯ
ПРОГРАММА рекурсивное_закрашивание (х, у, Ц_Г, Ц_З – целые)
. Система Предписаний (СП):
. . прочесть_пиксель (х, у – целые): атрибут_пикселя – целое
. . высветить_пиксель (х, у, атрибут – целое)
. Конец СП
. Типы:
. . С – целое
. Начало
. . С = прочесть_пиксель (х, у)
С – код цвета пикселя
. . Если С Ц_Г и С Ц_З То
. . . высветить_пиксель (х, у, Ц_З)
. . . рекурсивное_закрашивание (х – 1, у, Ц_Г, Ц_З)
. . . рекурсивное_закрашивание (х + 1, у, Ц_Г, Ц_З)
. . . рекурсивное_закрашивание (х, у – 1, Ц_Г, Ц_З)
. . . рекурсивное_закрашивание (х, у + 1, Ц_Г, Ц_З)
. . Конец Если
. Конец
КОНЕЦ рекурсивное_закрашивание.

7.

3.4.1. АЛГОРИТМ ПИКСЕЛЬНОГО
ЗАКРАШИВАНИЯ
Достоинства алгоритма: абсолютная
корректность заполнения области с границей
любой формы, с “дырками”, а также изящество и
краткость.
Недостатки:
• требования к объему стека возврата,
• требования к наличию рекурсии в языке,
• каждый пиксель приходится анализировать до
4-х раз (медленность).

8.

3.4.1. АЛГОРИТМ ПИКСЕЛЬНОГО
ЗАКРАШИВАНИЯ
6
5
4
3
2
1
0
0 1 2 3 4 5 6
. . С = прочесть_пиксель (х, у)
. . Если С Ц_Г и С Ц_З То
. . . высветить_пиксель (х, у, Ц_З)
. . . РЗ (х – 1, у, Ц_Г, Ц_З)
. . . РЗ (х + 1, у, Ц_Г, Ц_З)
. . . РЗ (х, у – 1, Ц_Г, Ц_З)
. . . РЗ (х, у + 1, Ц_Г, Ц_З)
. . Конец Если
1. РЗ(4, 2)
1.1.1.4.2. РЗ(3, 3)
1.1.1.4.2.2.4.1.1.
РЗ(2,
4)
1.1.1.4.2.4.
РЗ(3,
4)
1.1. РЗ(3, 2)
1.1.1.4.2.1.
РЗ(2,
3)
1.1.1.4.3. РЗ(2, 2)
1.1.1.4.2.2.4.1.2.
РЗ(4, 4)
1.1.1.
РЗ(2,
2)
1.1.1.4.2.2.
РЗ(4,
3)4)
1.1.1.4.2.2.4.1.3.
РЗ(3,
3)
1.1.1.4.4.
РЗ(2,
1.1.1.1. РЗ(1, 2)
РЗ(3, 3)
1.1.1.4.2.2.4.1.4. РЗ(3, 5) 1.1.1.4.2.2.1.
1.1.2. РЗ(4, 2)
1.1.1.2. РЗ(3,
2) 4)
1.1.1.4.2.2.2.
РЗ(5, 3)
1.1.3. РЗ(3, 1)
1.1.1.4.2.2.4.2.
РЗ(5,
1.1.1.3. РЗ(2,
1) 3)
1.1.1.4.2.2.3.
РЗ(4, 2)
1.1.4. РЗ(3, 3)
1.1.1.4.2.2.4.3.
РЗ(4,
1.1.1.4.2.2.4.
1.2. РЗ(5, 2) РЗ(4, 4)
1.1.1.4. РЗ(2,
3) 5)
1.1.1.4.2.2.4.4.
РЗ(4,
1.1.1.4.2.2.4.1.
РЗ(3, 4)
1.3.
РЗ(4, 1)
1.1.1.4.1.
1.1.1.4.2.3.
РЗ(3,РЗ(1,
2) 3)
1.4. РЗ(4, 3)