Algoritma garis Bresenhem adalah algoritma konversi penambahan nilai integer.
Langkah-langkah untuk membentuk garis menurut algoritma ini adalah :
Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.Tetukan titik disebelah kiri sebagai titik awal (x1,y1) dan titik lainnya sebagai titik akhir (x2, y2 ).Hitung Dx, Dy, dan 2Dy – 2Dx.Hitung parameter pk = 2Dy – Dx.Bandingkan if pk < 0 (xk+1, yk) else (xk +1, yk +1).A < 0 = 2 DyB > 0 = 2 Dy - 2Dx
Pk (+) = Pk + BPk (-) = Pk + A
Ulangi langkah nomor 5 untuk menentukan posisi pixel selanjutnya, sampai x = x2 dan y = y2.
Aturan Bresenham :
Jika Pk bernilai positif (+), maka tambahkan hasilnya dengan B dan nilai x dan y ditambah 1.
Jika Pk bernilai negatif (-), maka tambahkan hasilnya dengan A dan nilai x ditambah 1, sedangkan y ditambah 0 (tetap).
Putaran dihentikan jika koordinat x dan y sudah mencapai batas akhir.
Contoh Soal :
Titik Awal P1 (15,6) dan titik akhir P2 (28,13)
Hitung : Dx, Dy, 2Dy-2Dx
Dx = x2 - x1 = 28 – 15 = 13
Dy = y2 – y1 = 13 – 6 = 7
2 Dy – 2 Dx = 2(7) – 2(13) = 14 – 26 = -12
Hitung parameter pk = 2Dy – Dx
2(7) – (13) = 14 – 13 = 1
A < 0 = 2 Dy = 2 (7) = 14
B > 0 = 2 Dy – 2 Dx = 2(7) - 2(13) = 14 – 26 = -12
k
|
Pk
|
x
|
y
|
-
|
-
|
15
|
6
|
1
|
1
|
16
|
7
|
2
|
-11
|
17
|
7
|
3
|
3
|
18
|
8
|
4
|
-9
|
19
|
8
|
5
|
5
|
20
|
9
|
6
|
-7
|
21
|
9
|
7
|
7
|
22
|
10
|
8
|
-5
|
23
|
10
|
9
|
9
|
24
|
11
|
10
|
-3
|
25
|
11
|
11
|
11
|
26
|
12
|
12
|
-1
|
27
|
12
|
13
|
13
|
28
|
13
|