 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Bresenham's Line Algorithm
The Bresenham line algorithm [4] is an algorithm which determines which points in an n -dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics.
| х = x1; y = y1; Dх = abs(x2 - х1); Dу = abs(y2 - у1); s1 = Sign(х2 - х1); s2 = Sign(y2 - y1); | |
| If Dу > Dх then temp = Dх; Dх = Dу; Dу = temp; change = 1; else change = 0; end if | |
| e = 2Dy - Dx; | |
| for i = 1 to Dх Plot(x,y); while (е >= 0) If Обмен = 1 then x = x + s1; else y = y + s2; end if e = e - 2Dх; end while If Обмен = 1 then y = y + s2; else x = x + s1; end If e = e + 2Dy; next i finish |
To illustrate Bresenham line algorithm consider drawing of a segment from the point (0,0) to the point (-8, -4):
x1 = 0
у1 = 0
х2 = 8
y2 = 4
s1 = -1
s2 = -1
change = 0
e = 0
The results of steps through the main loop:
Table 4.1
| i | Plot | e | x | y |
| (0,0) | ||||
| -16 | -1 | |||
| -8 | -1 | -1 | ||
| (-1,-1) | ||||
| -2 | -1 | |||
| (-2,-1) | ||||
| -16 | -2 | -2 | ||
| -8 | -3 | -2 | ||
| (-3, -2) | ||||
| -4 | -2 | |||
| (-4,-2) | ||||
| -16 | -4 | -3 | ||
| -8 | -5 | -3 | ||
| (-5,-3) | ||||
| -6 | -3 | |||
| (-6,-3) | ||||
| -16 | -6 | -4 | ||
| -8 | -7 | -4 | ||
| (-7,-4) | ||||
| -8 | -4 |
Fig.4.2 demonstrates results of algoritm.
Fig.4.2. Drawing of a Segment from the Point (0,0) to the Point (-8, -4)
Поиск по сайту: