Цей алгоритм використовується для скан-конвертування рядка. Він був розроблений Bresenham. Це ефективний метод, оскільки він включає лише цілочисельні операції додавання, віднімання та множення. Ці операції можна виконувати дуже швидко, тому лінії можна швидко генерувати.

У цьому методі вибирається наступний піксель, який має найменшу відстань від справжньої лінії.

Метод працює наступним чином:

Припустимо піксель P₁'(x₁', і₁'), а потім виберіть наступні пікселі, коли ми працюємо з травнем до ночі, по одному пікселю за раз у горизонтальному напрямку до P₂'(x₂', і₂').

python або

Після пікселя виберіть будь-який крок

Наступний піксель

1. Або праворуч (нижня межа рядка)
2. Один зверху праворуч і вгору (верхня межа лінії)

Лінія найкраще апроксимується тими пікселями, які знаходяться на найменшій відстані від шляху між P₁',П₂'.

Вибирає наступний між нижнім пікселем S і верхнім пікселем T.
Якщо вибрано S
Маємо х_i+1=x_i+1 і у_i+1=y_i
Якщо вибрано T
Маємо х_i+1=x_i+1 і у_i+1=y_i+1

Фактичні координати y лінії при x = x_i+1є
y=mx_i+1+б

Відстань від S до фактичної лінії в напрямку y
s = y-y_i

Відстань від T до фактичної лінії в напрямку y
t = (у_i+1)-у

Тепер розглянемо різницю між цими двома значеннями відстані
s - t

Коли (s-t)<0 ⟹ s < t< p>

Найближчим пікселем є S

Коли (s-t) ≧0 ⟹ s

Найближчим пікселем є T

Ця різниця є
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Замінивши m на і введення змінної рішення
d_i=△x (s-t)
d_i=△x (2 (х_i+1)+2b-2y_i-1)
=2△xy_i-2△y-1△x.2b-2y_i△x-△x
d_i=2△y.x_i-2△x.y_i+c

Де c= 2△y+△x (2b-1)

алгоритм будки

Ми можемо записати змінну рішення d_i+1для наступного ковзання
d_i+1=2△y.x_i+1-2△x.y_i+1+c
d_i+1-д_i=2△y.(x_i+1-x_i)- 2△x(y_i+1-і_i)

Оскільки x_(i+1)=x_i+1, маємо
d_i+1+d_i=2△y.(x_i+1-х_i)- 2△x(y_i+1-і_i)

Особливі випадки

Якщо вибраний піксель знаходиться у верхньому пікселі T (тобто d_i≧0)⟹ і_i+1=y_i+1
d_i+1=d_i+2△y-2△x

Якщо вибраний піксель знаходиться в нижньому пікселі T (тобто d_i<0)⟹ y_{i+1=yi
di+1=di+2△р}

Нарешті обчислюємо d₁
d₁=△x[2m(x₁+1)+2b-2y₁-1]
d₁=△x[2(mx₁+б-у₁)+2m-1]

Оскільки mx₁+б-у_i=0 і m = , ми маємо
d₁=2△y-△x

Перевага:

1. Він включає лише цілу арифметику, тому він простий.

2. Це дозволяє уникнути генерації повторюваних точок.

3. Його можна реалізувати за допомогою апаратних засобів, оскільки він не використовує множення та ділення.

4. Він швидший порівняно з DDA (цифровим диференціальним аналізатором), оскільки він не включає обчислення з плаваючою комою, як алгоритм DDA.

Недолік:

1. Цей алгоритм призначений лише для базового малювання ліній. Ініціалізація не є частиною алгоритму ліній Брезенхема. Отже, щоб малювати плавні лінії, вам слід розглянути інший алгоритм.

Алгоритм лінії Брезенхема:

Крок 1: Алгоритм запуску

Крок 2: Оголосити змінну x₁,x₂,і₁,і₂,d,i₁,i₂,dx,dy

крок 3: Введіть значення x₁,і₁,x₂,і₂
Де x₁,і₁- це координати початкової точки
І х₂,і₂– координати Кінцевої точки

крок 4: Обчисліть dx = x₂-x₁
Обчисліть dy = y₂-і₁
Обчисліть i₁=2*ти
Обчисліть i₂=2*(dy-dx)
Обчисліть d=i₁-dx

перетворення nfa в dfa

крок 5: Розглянемо (x, y) як початкову точку та x_кінецьяк максимально можливе значення x.
Якщо dx<0
Тоді x = x₂
y = y₂
х_кінець=x₁
Якщо dx > 0
Тоді x = x₁
y = y₁
х_кінець=x₂

in.next java

крок 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₂-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

Програма для реалізації алгоритму малювання ліній Брезенхема:

 #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 та алгоритм лінії Брезенхама: