ALGORITMA DDA, BRESENHAM DAN MIDPOINT CIRCLE

1. Algoritma DDA (Digital Differensial Analyzer)

DDA adalah algoritma pembentukan garis berdasarkan perhitungan Δx dan Δy, menggunakan rumus y = m. Δ x. Garis dibuat dengan menentukan dua endpoint yaitu titik awal dan titik akhir. Setiap koordinat titik yang membentuk garis diperoleh dari perhitungan, kemudian dikonversikan menjadi nilai integer. Prinsip algoritma ini adalah mengambil nilai integer terdekat dengan jalur garis berdasarkan atas sebuah titik yang telah ditentukan sebelumnya (titik awal garis).

Langkah-langkah membentuk garis menurut algoritma DDA adalah :

• Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.

• Tentukan salah satu titik sebagai awal(x0,y0) dan titik akhir(x1,y1). 3. 

• Hitung dx=x1¬x0, dan dy= y1¬y0. 4.

• Tentukan langkah, yaitu dengan cara jarak maksimum jumlah penambahan nilai x maupun nilai y, dengan cara:

• Bila nilai absolut dari dx lebih besar dari absolut dy, maka langkah= absolut dari dx. ¬Bila tidak maka langkah= absolutdari dy

• Hitung penambahan koordinat pixel yaitu x_increment = Δx / step dan y_increment = Δy / step

• Koordinat selanjutnya (x+x_increment, y+y_increment)

• Posisi pixel pada layar ditentukan dengan pembulatan nilai koordinat tersebut.

• Ulangi nomor 6 dan 7 untuk menentukan posisi pixel selanjutnya,sampai x=x1 dan y=y1.

2. Algoritma Bresenham

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

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 membuat garis menggunakan algoritma bresenham adalah :

• Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.  

• Tetukan salah satu titik disebelah kiri sebagai titik awal (x0, y0) dan titik lainnya sebagai titik akhir (x1, y1 ). 

• Hitung Δx, Δy, Δ2x, dan 2Δy – 2Δx. 

• Hitung parameter p0 = 2Δy – Δx. 

• Untuk setiap xk sepanjang jalur garis, dimulai dengan k = 0 

• bila pk <0 maka titik selanjutnya (xk+1, yk) dan pk+1 = pk +2Δy

• bila tidak maka titik selanjutnya adalah (xk+1, yk+1) 

• dan pk+1=pk+2Δ-y2Δx. 

• Ulangi langkah nomor 5 untuk menentukan posisi pixel selanjutnya, sampai x=xn

Sangat terlihat bahwa perbedaan algoritma DDA dan Bresenham ada di penentuan pixel selanjutnya, dan juga penggunaan bilangan real dan integer, pada DDA, dia menggunakan bilangan real, dan perlu pembulatan pada eksekusi ke pixelnya, pada bresenham, sudah menggunakan nilai integer yang sudah siap untuk eksekusikan ke dalam bentuk pixel, jadi secara teori, algoritma Bresenham akan lebih cepat dibanding algoritma DDA karena sudah menggunakan integer yang lebih cepat eksekusinya.

Contoh : 

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

x = x1– x0 dan y= y1 – y0 

x = 7 dan y = 6 

parameter p0 = 2Δy – x

p0 = 5 

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

3. Algoritma Mid-point

Algoritma yang digunakan membentuk semua titik berdasarkan titik pusat dengan penambahan semua jalur sekeliling lingkaran. Algoritma ini diturunkan dari algoritma Midpoint untuk pembentukan garis. Dalam hal ini hanya diperhatikan bagian 45’ dari suatu lingkaran, yaitu oktan kedua dari x=0 ke x=R/√2, dan menggunakan CirclePoints untuk menampilkan titik dari seluruh lingkaran. Langkah langkah untuk membentuk lingkaran algoritma Circle Midpoint: 

• Tentukan radius r dengan titk pusat lingkaran(xc,yc) kemudian diperoleh (x0,y0)=(0,r) 

• Hitung nilai dari parameter P0=5/4¬r 

• Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut: 

Bila Pk<0,  maka titik selanjutnya adalah (xk+1,yk))dan  Pk+1=Pk+2xk+1+1

Bila tidak, maka selanjutnya adalah(xk+1,yk¬1), dan Pk+1=Pk+2xk+1+1¬ 2yk+1 Dimana 2xk+1=2xk+2 dan 2yk+=2yk¬2

• Tentukan titik simetris pada ketujuh oktan yang lain 

• Gerakkan setiap posisi pixel(x,y) pada garis melingkar dari lingkaran dengan titik pusat (xc,yc) dan tentukan nilai koordinat: x=x+xcy=y+yc 

• Ulangi langkah ke¬3 sampai 5, sehingga x>=y

Contoh algoritma lingkaran midpoint
Untuk menggambarkan algoritma Bressenham dalam pembentukan suatu lingkaran dengan titik pusat (0,0) dan radius 10, perhitungan berdasarkan pada oktan dari kuadran pertama di mana x=0 sampai x=y. Nilai parameter dapat ditentukan dengan P0=1¬r =1¬10=¬9 Koordinat titk awal adalah (x,r)=(0,8)