Pembentukan Garis dengan Algoritma Bressenham

Algoritma Bressenham

Prosedur yang terdapat pada algoritma ini adalah untuk menggambar kembali garis dengan membulatkan nilai x atau y kebilangan integer dengan membutuhkan waktu, serta variable x,y dan m yang merupakan bilangan real karena kemiringan merupakan nilai pecahan. Algoritma Bressenham ini mengembangkan algoritma klasik yang lebih menarik, karena hanya menggunakan perhitungan matematika dengan bilangan integer. Dengan ini tidak perlu membulatkan nilai posisi setiap pixel setiap waktu. Algoritma garis Bressenham disebut juga midpoint line algorithm karena algoritma konversi penambahan nilai integer yang juga dapat diadaptasi untuk menggambar sebuah lingkaran.

Langkah-langkah untuk membentuk garis menurut algoritma ini adalah :

1)                    .Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.

2)                  Tetukan salah satu titik disebelah kiri sebagai titik awal (x₀, y₀) dan titik lainnya sebagai titik akhir (x₁, y₁ ).

3)                  Hitung  Δx,  Δy, Δ2x, dan 2Δy – 2Δx.

4)                  Hitung parameter p₀ = 2Δy – Δx.

5)                  Untuk setiap x_k sepanjang jalur garis, dimulai dengan k = 0

·                     bila p_k <0 maka titik selanjutnya (x_k+1, y_k) dan p_k+1 = p_k +2Δy

·                     bila tidak maka titik selanjutnya adalah (x_k+1, y_k+1)                 

dan p_k+1=p_k+2Δ-y2Δx.

6)                  Ulangi langkah terakhir untuk menentukan posisi pixel selanjutnya, sampai x=x_n.

Contoh :

Untuk menggambarkan suatu algoritma Bressenham dalam pembentukan suatu garis yang menghubungkan antara titik (10,10) dan (17,16), pertama-tama ditentukan bahwa titik (10,10) berada disebelah kiri yang merupakan titik awal, sedangkan (17,16) merupakan titik akhir. Posisi yang membentuk garis dapat ditentukan dengan perhitungan dibawah ini :

·                     x = x₁– x₀ dan  y= y₁ – y₀

x = 7 dan  y = 6

·                     parameter p₀ = 2Δy –  x

p₀ = 5

·                     increment 2Δy = 12      2Δy – 2Δx = -2

 Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Jadi, Algoritma Bressenham ini merupakan algoritma pembentukan garis berdasarkan selisih antara garis yang diinginkan terhadap setengah ukuran dari pixel yang sedang digunakan.