Този алгоритъм се използва за сканиране, конвертиране на ред. Разработен е от 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_аз

замяна на метод в java

Разстоянието от Т до действителната линия в посока у
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. Така че, за да рисувате гладки линии, трябва да потърсите различен алгоритъм.

заместване от низ в java

Алгоритъм на линията на 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) координати.

ctc пълна форма

Стъпка 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: