Този алгоритъм се използва за сканиране, конвертиране на ред. Разработен е от Bresenham. Това е ефективен метод, тъй като включва само цели събиране, изваждане и операции за умножение. Тези операции могат да се извършват много бързо, така че линиите могат да се генерират бързо.

При този метод следващият избран пиксел е този, който има най-малко разстояние от истинската линия.

Методът работи по следния начин:

Да приемем пиксел P ₁ '(х ₁ ',и ₁ '), след това изберете следващите пиксели, докато работим с нашия май до нощта, позиция по един пиксел в хоризонтална посока към P ₂ '(х ₂ ',и ₂ ').

Веднъж влязъл пиксел, изберете всяка стъпка

Следващият пиксел е

1. Или този отдясно (долната граница за линията)
2. Едната е отгоре надясно и нагоре (горна граница за линията)

Линията се апроксимира най-добре от онези пиксели, които попадат на най-малко разстояние от пътя между P ₁ ',P ₂ '.

Избира следващия между долния пиксел S и горния пиксел T.
Ако е избран S
Имаме х _i+1 =x _аз +1 и г _i+1 =г _аз
Ако е избрано T
Имаме х _i+1 =x _аз +1 и г _i+1 =г _аз +1

Действителните y координати на линията при x = x _i+1 е
y=mx _i+1 +б

Разстоянието от S до действителната линия в посока y
s = y-y _аз

Разстоянието от Т до действителната линия в посока у
t = (y _аз +1)-y

Сега помислете за разликата между тези 2 стойности на разстоянието
s - t

когато (т-т) <0 ⟹ s < t < p>

Най-близкият пиксел е S

Когато (s-t) ≧0 ⟹ s

Най-близкият пиксел е T

Тази разлика е
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Замествайки m с и въвеждане на променлива за решение
д _аз =△x (s-t)
д _аз =△x (2 (х _аз +1)+2b-2y _аз -1)
=2△xy _аз -2△y-1△x.2b-2y _аз △x-△x
д _аз =2△y.x _аз -2△x.y _аз +c

Където c= 2△y+△x (2b-1)

Можем да напишем променливата за решение d _i+1 за следващото приплъзване
д _i+1 =2△y.x _i+1 -2△x.y _i+1 +c
д _i+1 -д _аз =2△y.(x _i+1 -х _аз )- 2△x(y _i+1 -и _аз )

Тъй като x_(i+1)=x _аз +1, имаме
д _i+1 +г _аз =2△y.(x _аз +1-х _аз )- 2△x(y _i+1 -и _аз )

Специални случаи

Ако избраният пиксел е в горния пиксел T (т.е. d _аз ≧0)⟹ и _i+1 =г _аз +1
д _i+1 =d _аз +2△y-2△x

Ако избраният пиксел е най-долният пиксел T (т.е. d _аз <0)⟹ y _{i+1=y аз
д i+1 =d аз +2△г}

Накрая изчисляваме d ₁
д ₁ =△x[2m(x ₁ +1)+2b-2y ₁ -1]
д ₁ =△x[2(mx ₁ +б-у ₁ )+2m-1]

Тъй като mx ₁ +б-у _аз =0 и m = , ние имаме
д ₁ =2△y-△x

Предимство:

1. Включва само аритметика с цели числа, така че е проста.

2. Избягва генерирането на дублирани точки.

3. Може да се реализира с помощта на хардуер, защото не използва умножение и деление.

4. Той е по-бърз в сравнение с DDA (цифров диференциален анализатор), тъй като не включва изчисления с плаваща запетая като алгоритъма DDA.

Недостатък:

1. Този алгоритъм е предназначен само за базово чертане на линии. Инициализирането не е част от алгоритъма за линии на Bresenham. Така че, за да рисувате гладки линии, трябва да потърсите различен алгоритъм.

Алгоритъм на линията на Bresenham:

Етап 1: Стартирайте алгоритъма

Стъпка 2: Декларирайте променлива x ₁ ,х ₂ ,и ₁ ,и ₂ ,d,i ₁ ,i ₂ ,dx,dy

Стъпка 3: Въведете стойност на x ₁ ,и ₁ ,х ₂ ,и ₂
Където x ₁ ,и ₁ са координатите на началната точка
и х ₂ ,и ₂ са координатите на крайната точка

Стъпка 4: Изчислете dx = x ₂ -х ₁
Изчислете dy = y ₂ -и ₁
Изчислете i ₁ =2*ти
Изчислете i ₂ =2*(dy-dx)
Изчислете d=i ₁ -dx

Стъпка 5: Разгледайте (x, y) като начална точка и x _край като максимална възможна стойност на x.
Ако dx <0
Тогава x = x ₂
y = y ₂
х _край =x ₁
Ако dx > 0
Тогава x = x ₁
y = y ₁
х _край =x ₂

Стъпка 6: Генериране на точка при (x,y) координати.

Стъпка 7: Проверете дали е генериран цял ред.
Ако x > = x _край
Спри се.

Стъпка 8: Изчислете координатите на следващия пиксел
Ако d <0
Тогава d = d + i ₁
Ако d ≧ 0
Тогава d = d + i ₂
Увеличете y = y + 1

Стъпка 9: Увеличете x = x + 1

Стъпка 10: Начертайте точка с най-новите (x, y) координати

Стъпка 11: Отидете на стъпка 7

Стъпка 12: Край на алгоритъма

Пример: Началната и крайната позиция на линията са (1, 1) и (8, 5). Намерете междинни точки.

Решение: х ₁ =1
и ₁ =1
х ₂ =8
и ₂ =5
dx= x ₂ -х ₁ =8-1=7
вие=г ₂ -и ₁ =5-1=4
аз ₁ =2* ∆y=2*4=8
аз ₂ =2*(∆y-∆x)=2*(4-7)=-6
d = I ₁ -∆x=8-7=1

Програма за прилагане на алгоритъма за чертане на линия на Bresenham:

 #include #include void drawline(int x0, int y0, int x1, int y1) { int dx, dy, p, x, y; dx=x1-x0; dy=y1-y0; x=x0; y=y0; p=2*dy-dx; while(x=0) { putpixel(x,y,7); y=y+1; p=p+2*dy-2*dx; } else { putpixel(x,y,7); p=p+2*dy;} x=x+1; } } int main() { int gdriver=DETECT, gmode, error, x0, y0, x1, y1; initgraph(&gdriver, &gmode, 'c:\turboc3\bgi'); printf('Enter co-ordinates of first point: '); scanf('%d%d', &x0, &y0); printf('Enter co-ordinates of second point: '); scanf('%d%d', &x1, &y1); drawline(x0, y0, x1, y1); return 0; }  

Изход:

Правете разлика между DDA алгоритъм и алгоритъм на Bresenham's Line: