Компьютерная графика ч1

62

Вершины многоугольника заданы пикселями (1,0), (7,0), (8,1), (8,4), (6,6), (1,6), (0,5) и (0,1). Внутренняя дыра определяется пикселями (3,2), (5,2), (5,3), (3,3). Затравочный пиксель

— (4,4). Порядок заполнения указан на рисунке линией со стрелками. Числа в квадратике пикселя показывают позицию в стеке, занимаемую пикселем. Когда обработка доходит до пикселя (3,1), все окружающие его 4-связные пиксели либо уже заполнены, либо являются граничными. Поэтому ни один из пикселей не помещается в стек. Глубина стека в этот момент равна 15. В стеке находятся пиксели (7,1), (7,2), (7,3), (6,5), (7,4), (6,5), (3,1), (1,2), (1,3), (1,4), (2,5), (3,5), (4,5), (5,4).

После удаления из стека пикселя (7,1) заполняется колонка (7,1), (7,2), (7,3), (7,4), при этом ни один новый пиксель в стек не добавляется. Для пикселя (7,4) снова все 4-связные окружающие пиксели либо уже заполнены, либо являются граничными. Обращаясь к стеку, алгоритм извлекает пиксель (6,5), его заполнение завершает заполнение всего многоугольника. Дальнейшая o6работка происходит без какого-либо заполнения, и когда стек становится пустым, алгоритм завершает работу.

Построчный алгоритм заполнения с затравкой

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

Данный алгоритм применим к гранично-определенным областям. Граничноопределенная 4-связная область может быть как выпуклой, так и не выпуклой, а также может содержать дыры. В области, внешней и примыкающей к нашей гранично-определенной области, не должно быть пикселей с цветом, которым область или многоугольник заполняется. Схематично работу алгоритма можно разбить на четыре этапа.

1. Затравочный пиксель на интервале извлекается из стека, содержащего затравочные пиксели.

63

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

3.В переменных Хлев и Хправ запоминаются крайний левый и крайний правый пиксели интервала.

4.В диапазоне Хлев <= x <= Xправ проверяются строки, расположенные непосредственно над и под текущей строкой. Определяется, есть ли на них еще не заполненные пиксели. Если такие пиксели есть (т. е. не все пиксели граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксель в каждом интервале отмечается как затравочный и помещается в стек.

5.При инициализации алгоритма в стек помещается единственный затравочный пиксель, работа завершается при опустошении стека.

Как показано в примере ниже, алгоритм справляется с дырами и зубцами на границе. Ниже приводится более подробное описание алгоритма на псевдокоде:

Затравка (х,у) - выдает затравочный пиксель Pop - процедура, которая извлекает пиксель из стека Push - процедура, которая помещает пиксель в стек

Push Затравка (х, у) while (стек не пуст)

Pop Пиксель (х, у)

Пиксель (х, у) = Нов_значение Врем_х = х

х = х + 1

while Пиксель (х, у) <> Гран_значение Пиксель (х, у) = Нов_значение х = х + 1

end while

Хправ = х — 1

х= Врем_х

х= х — 1

while Пиксель (х, у) <> Гран_значение Пиксель (х, у) = Нов_значение х = х — 1

end while

Хлев = х + 1

х= Врем_х

х= Хлев

у = у + 1

while х <= Хправ

Флаг = 0

while (Пиксель (х, у) <> Гран_значение and Пиксель (х, у) <> Нов_значение and х < Хправ if Флаг = 0 then Флаг = 1

x = x + 1 end while

/инициализируем стек

/извлекаем пиксель из стека и присваиваем ему новое значение

/сохраняем x-координату затравочного пикселя

/заполняем интервал справа от затравки

/сохраняем крайний справа пиксель

/восстанавливаем х-координату затравки

/заполняем интервал слева от затравки

/сохраняем крайний слева пиксель

/восстанавливаем х-координату затравки

/проверим, что строка выше не является ни границей многоугольника, ни ухе полностью заполненной; если это не так, то найти затравку, начиная с левого края подынтервала сканирующей строкивосстанавливаем х-координату затравки

/ищем затравку на строке выше

64
if Флаг = 1 then	/ помещаем в стек крайний справа пиксел
if (x = Хправ and Пиксель (х, у) <> Гран_значение and
Пиксель (х, у) <> Нов_значение) then
Push Пиксель (х, у)
elsePush Пиксель (х — 1, у)
end if
Флаг = 0
end If
Хвход = х	/ продолжим проверку, если интервал был
while ((Пиксель (х, у) = Гран_значение оr	прерван
Пиксель (х, у) = Нов_значение) and х < Хправ)
х = х + 1
end while
if х = Хвход then х = х + 1	/ удостоверимся, что координата пикселя
end while	увеличена
эта часть алгоритма совершенно аналогична проверке	/ проверим, что строка ниже не является ни
для строки выше, за исключением того, что вместо y =	границей многоугольника, ни уже полностью
y + 1 надо подставить y = y — 1	заполненной
end while
finish

Пример 2.4. Построчный алгоритм заполнения с затравкой. Рассмотрим работу алгоритма для гранично-определенной области на рис. 2.16. При инициализации в стек помешается затравочный пиксел, помеченный как Затравка (5,7) на рис. 2.16,а. Первоначально в качестве затравки интервала из стека извлекается этот пиксел. Интервал заполняется справа и слева от затравки. Найденные при этом концы интервала Хправ = 9 и Xлев = 1. Затем проверяется строка, расположенная выше текущей и оказывается, что она не граничная и не заполненная. Крайним правым пикселем в диапазоне 1 <= x <= 9 оказывается пиксель (8,8), помеченный цифрой 1 на рис. 2.16,а. Этот пиксель помещается в стек. Затем аналогичным образом обрабатывается строка ниже текущей. В диапазоне Хлев <= x <= Xправ есть два подинтервала на этой стороне. Для левого интервала в качестве затравки выступает пиксель (3,6), помеченный цифрой 2 на рис. 2.16,а, он тоже помещается в стек. Затравка для правого подинтервала - пиксель (9,6), он помещается в стек. Заметим, что пиксель (9,6) - не самый крайний правый пиксель на интервале, однако это самый крайний правый пиксель в

диапазоне Хлев <= x <= Xправ, т.е. в диапазоне 1 <= x <= 9. На этом завершается первый проход алгоритма.

65

Далее из стека извлекается верхний пиксель. Здесь заполняются интервалы, расположенные в правой части многоугольника на последовательных сканирующих строках (рис. 2.16, b, c, d). Для строки 3 затравкой служит пиксель (10,3) (рис. 2.16, d). В результате заполнения интервала справа и слева от затравки получаем новые пределы диапазона Хправ = 10 и Xлев = 1. Обрабатывая строку выше, получаем для основного подынтервала затравочный пиксель (3,4), который помещается в стек. Правый подинтервал к этому времени уже заполнен. Обработка строки ниже дает затравку (3,2) для левого и (10,2) для правого подынтервалов. Эти пиксели также помещаются в стек. Именно сейчас достигается максимальная глубина стека для обрабатываемого многоугольника.

66

Теперь остается только один интересный момент. После заполнения 4-связных полигональных подобластей с затравочными пикселями 5, 4 и 3 на рис. 2.16,е из стека извлекается пиксель, помеченный цифрой 2. Здесь мы обнаруживаем, что все пиксели на этой строке уже и на соседних строках (выше и ниже) уже заполнены. Таким образом, ни один пиксель в стек не помещается. Из стека извлекается пиксель 1 и строка обрабатывается, при этом вновь добавочных пикселей не появляется. Теперь стек пуст, многоугольник заполнен и работа алгоритма завершена.

По сравнению с алгоритмом из разд. 2.7 максимальная глубина стека в этом примере равна пяти.

Лабораторные основы

Цель работы: изучить рекурсивный алгоритм закраски произвольно нарисованной области.

Основные понятия, используемые в лабораторной работе: Закраска объектов и областей. Рекурсия. 4-х связные и 8-и связные области.

Рекурсией в программировании называется вызов функции из тела самой функции. Таким образом, рекурсивная функция – это функция, вызывающая сама себя. Пример рекурсивной функции вычисления факториала числа.

Private … Factorial …

If N=1 Then Factorial=1

If N>1 Then Factorial = N*Factorial(N-1) End …

При решении задач закраски выделяют четырёхсвязные и восьмисвязные области.

+y

-x +x

-y

x, y+1	x-1, y+1	x+1, y+1

x-1, y x+1, y

x-1, y-1

x+1, y-1

x, y-1

67

Словарь основных терминов среды Visual Basic

Англо-русский словарь

	A		K
	Alignment	Выравнивание	Key	Клавиша
	AutoRedraw	Автоматическая перерисовка	L
	AutoSize	Автоподстройка размера	Label	Метка (этикетка)
	B		Left	Левый, X-координата левого верхнего
				угла объекта
	BackColor	Цвет фона	Line	Линия, строка
	BorderStyle	Тип границ	List	Список
	BorderWidth	Ширина границы	ListBox	Список (объект)
	Box	Коробка	Load	Загрузить
	Button	Клавиша	Long	Длинный целый (тип данных)
	C		M
	Caption	Название (ярлык)	Mouse	Мышь
	Character	Символ	Move	Двигать, перемещать
	CheckBox	Флажок	N
	Circle	Окружность	Next	Следующий
	Clear	Чистый	O
	Click	Щелчок	Object	Объект
	CommandButton	Командная кнопка	OptionButton	Переключатель
	Cross	В клеточку	P
	Currency	С фиксированной точкой (тип	Paint	Рисовать
		данных)
	Current	Текущий	Pixel	Пиксел
	D		Point	Точка
	Data	Данные	Procedure	Процедура
	DblClick	Двойной щелчок	Project	Проект
	Delete	Стереть (удалить)	Property(Properties)	Свойство (свойства)
	Diagonal Cross	В косую клеточку	R
	Dim(Dimension)	Массив	Rectangle	Прямоугольник
	Double	Двойной (тип данных)	Right	Правый
	Down	Вниз	Run	Запустить (выполение программы)
	Downward Diagonal	Диагоналями справа налево	S
	Draw	Рисовать	Save	Сохранить
	DrawMode	Режим рисования	Save as…	Сохранить как …
	DrawStyle	Стиль рисования	Scale	Масштаб
	DrawWidth	Толщина рисования	ScaleMode	Единица измерения
	E		ScrollBars	Линейки прокрутки
	Edit	Редактировать	Set	Установить
	Else	Иначе (в противном случае)	Shape	Фигура
	Enabled	Разрешенный	Single	Вещественный,одинарной точности
				(тип данных)
	End	Конец	Solid	Сплошной
	Exit	Выход	Step	Шаг
	F		String	Строка
	False	Ложь	Square	Квадрат
	FillColor	Цвет заполнения	T
	FillStyle	Стиль заполнения	TextBox	Текстовое окно
	Font	Шрифт	Timer	Таймер
	FontBold	Полужирный шрифт	Toolbox	Панель инструментов
	FontItalic	Курсив	Top	Верх, Y-координата левого верхнего
				угла объекта
	FontName	Название шрифта	Transparent	Прозрачный
	FontSize	Размер шрифта	True	Истина

			68
FontStrikethru	Зачеркнутый шрифт		Twip		1/1440 дюйма (0.00175 см)
FontUnderline	Подчеркнутый шрифт			U
For	Для		Upward Diagonal		Диагоналями слева направо
ForeColor	Основной цвет			V
Form	Форма		Vertical Line		Вертикальная линия
Frame	Рамка		View		Вид
G			Visible		Видимый
General	Общий		VScrollBar		Вертикальная линейка прокрутки
H				W
Height	Высота		Width		Ширина
Help	Помощь		WindowState		Состояние окна
Horizontal Line	Горизонтальная линия
HscrollBar	Горизонтальная линейка
	прокрутки
I
Icon	Значок (иконка)
Image	Изображение
Inch	Дюйм
Insert	Вставить
Integer	Целый (тип данных)
		Русско-английский словарь
А				П
Автоматическая перерисовка		AutoRedraw		Панель инструментов		Toolbox
Автоподстройка размера		AutoSize		Переключатель		OptionButton
В				Пиксел		Pixel
В клеточку		Cross		Подчеркнутый шрифт		FontUnderline
В косую клеточку		Diagonal Cross		Полужирный шрифт		FontBold
Вертикальная линейка		VScrollBar		Помощь		Help
прокрутки
Вертикальная линия		Vertical Line		Правый		Right
Верх, Y-координата левого		Top		Проект		Project
верхнего угла объекта
Вещественный,одинарной		Single		Прозрачный		Transparent
точности (тип данных)
Вид		View		Процедура		Procedure
Видимый		Visible		Прямоугольник		Rectangle
Вниз		Down		Р
Вставить		Insert		Размер шрифта		FontSize
Выравнивание		Alignment		Разрешенный		Enabled
Высота		Height		Рамка		Frame
Выход		Exit		Редактировать		Edit
Г				Режим рисования		DrawMode
Горизонтальная линейка		HScrollBar		Рисовать		Draw
прокрутки
Горизонтальная линия		Horizontal Line		Рисовать		Paint
Д				С
Данные		Data		С фиксированной точкой (тип		Currency
				данных)
Двигать, перемещать		Move		Свойство (свойства)		Property(Properties)
Двойной (тип данных)		Double		Символ		Character
Двойной щелчок		DblClick		Следующий		Next
Диагоналями слева направо		Upward Diagonal		Состояние окна		WindowState
Диагоналями справа налево		Downward Diagonal		Сохранить		Save
Длинный целый (тип данных)		Long		Сохранить как …		Save as…
Для		For		Список		List

		69
Дюйм	Inch	Список	ListBox
Е		Сплошной	Solid
Единица измерения	ScaleMode	Стереть (удалить)	Delete
З		Стиль заполнения	FillStyle
Загрузить	Load	Стиль рисования	DrawStyle
Запустить (выполение	Run	Строка	String
программы)
Зачеркнутый шрифт	FontStrikethru	Т
Значок (иконка)	Icon	Таймер	Timer
И		Твип = 1/1440 дюйма или	Twip
		0.00175 см
Изображение	Image	Текстовое окно	TextBox
Иначе (в противном случае)	Else	Текущий	Current
Истина	True	Тип границ	BorderStyle
К		Толщина рисования	DrawWidth
Квадрат	Square	Точка	Point
Клавиша	Button	У
Клавиша	Key	Установить	Set
Командная кнопка	CommandButton	Ф
Конец	End	Фигура	Shape
Коробка	Box	Флажок	CheckBox
Курсив	FontItalic	Форма	Form
Л		Ц
Левый, X-координата левого	Left	Цвет заполнения	FillColor
верхнего угла объекта
Линейки прокрутки	ScrollBars	Цвет фона	BackColor
Линия, строка	Line	Целый (тип данных)	Integer
Ложь	False	Ч
М		Чистый	Clear
Массив	Dim(Dimension)	Ш
Масштаб	Scale	Шаг	Step
Метка (этикетка)	Label	Ширина	Width
Мышь	Mouse	Ширина границы	BorderWidth
Н		Шрифт	Font
Название (ярлык)	Caption	Щ
Название шрифта	FontName	Щелчок	Click
О
Общий	General
Объект	Object
Окружность	Circle
Основной цвет	ForeColor

70

Список использованной литературы

1.Роджерс Д., Адамс Дж. Математические основы машинной графики. – М.: Машиностроение, 1980

2.Шикин Е.В., Плис А.И. Кривые и поверхности на экране компьютера. – М.: Диалог-МИФИ, 1996

3.Фокс А., Прат М. Вычислительная геометрия. Применение в проектировании и на производстве. – М.: Мир, 1982

4.Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики.

– СПб.: БХВ-Петербург, 2003

5.Разин И.Б. Курс лекций по ГММГ

6.Лукин С.Н. Visual Basic. – М.: Диалог-МИФИ, 2003