Algoritma Bresenham

Salah satu dari algoritma menggambar garis dalam grafika komputer adalah algoritma Bresenham, dikembangkan oleh Jack Bresenham pada tahun 1962 di IBM.

Cara kerja dari algoritma ini adalah memeriksa garis yang telah diubah hanya dengan menggunakan perhitungan integer yang terus bertambah yang bisa diadaptasikan untuk menampilkan lingkaran dan bentuk kurva yang lain.

Langkah-langkah dalam algoritma Bresenham adalah:

1. Input dua titik, dan simpan titik yang paling kiri sebagai (x₀,y₀)
2. Plotkan titik pertama tersebut
3. Hitunglah ∆x, ∆y, 2∆y dan 2∆y-2∆x serta perolehlah nilai awal parameter keputusan sbb: _{p0 =} 2∆y-∆x
4. Setiap x_k sepanjang garis, mulai dari k = 0, lakukan pengujian sbb:
   Apabila pk < 0, maka titik berikutnya yang akan diplot adalah(x_k+1,_yk), kemudian _: p_k+1 = pk+ 2∆y
   
   _{Apabila Sebaliknya,maka titik berikutnya bernilai (xk+1,yk+1), lalu perhitungannya:     pk+1 = pk+ 2∆y- 2∆x}                                                              
5.  Ulangi langkah 4 sebanyak ∆x kali.

Berikut ini adalah contoh bagaimana menentukan posisi titik-titik yang digunakan untuk membentuk sebuah garis menggunakan algoritma Bresenham.

Misalkan ada dua buah titik dengan koordinat (20,10) dan (30,18)

Untuk langkah awal, kita akan menghitung:
∆x=30-20=10, ∆y=18-10=8, 2∆y=16 dan 2∆y-∆x=-4

nilai parameter keputusannya adalah:
_{p0 =} 2∆y-∆x=6

Dengan begitu kita bisa menghitung semua titiknya sehingga hasilnya dapat dijabarkan dalam tabel sbb:

Referensi

Hearn,Baker.Computer Graphics C Version Second Edition
www.wikipedia.org/wiki/Bresenham's_line_algorithm