Алгоритм Брезенхема разложения в растр отрезка для первого октанта

предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают

Integer - функция преобразования в целое

x, y, x, y - целые

е - вещественное

инициализация переменных

x = x1

y = y1

x = x2 - x1

y = y2 - y1

Инициализация с поправкой на половину пиксела

е = y/x - 1/2

начало основного цикла

for i = 1 to x

plot (x,y)

while (e => 0)

y = y + 1

e = e - 1

end while

x = x + 1

e = e + y/x

next i

finish

Блок-схема алгоритма приводится на рис.3.3. Пример приведен ниже.

Рис. 3.3. Блок-схема алгоритма Брезенхема.

Пример 3.1. Алгоритм Брезенхема.

Рассмотрим отрезок проведенный из точки (0,0) в точку (5,5). Разложение отрезка в растр по алгоритму Брезенхема приводит к такому результату:

начальные установки

x = 0

y = 0

x = 5

y = 5

е = 1 - 1/2 = 1/2

результаты работы пошагового цикла

i	Plot	e	x	y
		1/2
	(0,0)
		-1/2
		1/2
	(1,1)
		-1/2
		1/2
	(2,2)
		-1/2
		1/2
	(3,3)
		-1/2
		1/2
	(4,4)
		-1/2
		1/2

Результат показан на рис.3.4 и совпадает с ожидаемым. Заметим, что точка растра с координатами (5,5) не активирована. Эту точку можно активировать путем изменения цикла for-next на 0 to x. Активацию точки (0,0) можно устранить, если поставить оператор Plot непосредственно перед строкой next i.

Рис. 3.4. Результат работы алгоритма Брезенхема в первом октанте.

В следующем разделе описан общий алгоритм Брезенхема.