Algoritma DDA, Bressenham, dan Midpoint Circle

 Algoritma DDA

• Pengertian Algoritma

Algoritma adalah metode efektif diekspresikan sebagai rangkaian terbatas  dari instruksi-instruksi yang telah didefinisikan dengan baik untuk menghitung sebuah fungsi.

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. Langkah-langkah pembentukan menurut algoritma DDA, yaitu :

1. Tentukan dua titik yang akan dihubungkan.
2. Tentukan salah satu titik sebagai titik awal (x0, y0) dan titik akhir (x1, y1).
3. Hitung Δx = x1 – x0 dan  Δ y = y1 – y0.
4. Tentukan step, yaitu jarak maksimum jumlah penambahan nilai x maupun nilai y dengan cara :

• bila nilai |Δy| > |Δx| maka step = nilai |Δy|.
• bila tidak maka step = |Δx|.

5. Hitung penambahan koordinat pixel yaitu x_increment = Δx / step dan y_increment =  Δy / step.
6. Koordinat selanjutnya (x+x_incerement, y+y_increment).
7. Posisi pixel pada layer ditentukan dengan pembulatan nilai koordinasi tersebut.
8. Ulangi step 6 dan 7 untuk menentukan posisi pixel selanjutnya, sampai x = x1 dan y = y1

 

Contoh :

Untuk menggambarkan algoritma DDA dalam pembentukan suatu garis yang menghubungkan titik (10,10) dan (17,16), pertama-tama ditentukan dx dan dy, kemudian dicari step untuk mendapatkan x_increment dan y_increment.

Δx = x1 – x 0 = 17-10 = 7

Δy = y1 – y0  = 16 -10 = 6

selanjutnya hitung dan bandingkan nilai absolutnya.

|Δx| = 7

|Δy| = 6

karena |Δx| > |Δy|, maka step = |Δx| = 7, maka diperoleh :

x_inc = 7/7= 1

y_inc = 6/7 = 0,86 .

ALGORITMA BRESENHAM

Untuk menggambarkan piksel-piksel dalam garis lurus, parameter yang digunakan tergantung dari gradient, jika besarnya gradient diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai hasil dari fungsi, sebaliknya, bila gradient melebihi 1, maka sumbu y digunakan sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan untuk menghindari terjadinya gaps karena adanya piksel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan real, sedangkan koordinat pixel dinyatakan dalam bilangan integer (x,y), maka diperlukan operasi pembulatan kedalam bentuk integer terdekat. Penggambaran garis lurus dengan metode diatas dimulai dengan operasibilangan real untuk menghitung gradient m dan konstanta c.

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.

Inti dari Algoritma Bresenham hanya menentukan apakah langkah selanjutnya (xk+1,yk) atau (xk+1,yk+1).

Hal itu ditentukan oleh nilai Pk yang diperoleh dari Pk = 2∆y-∆x

Jika Pk < 0, maka langkah selanjutnya adalah (xk+1,yk), dan Pk+1 = Pk+ 2∆y,

Jika tidak, maka langkah selanjutnya adalah (xk+1,yk+1), dan Pk+1 = Pk+ 2∆y- 2∆x.

Langkah-langkah membuat garis menggunakan algoritma bresenham adalah :

1. Input dua titik, dan simpan titik yang paling kiri sebagai (x0,y0) 
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 xk sepanjang garis, mulai dari k = 0, lakukan pengujian sbb: 
5. Apabila pk < 0, maka titik berikutnya yang akan diplot adalah(xk+1,yk), kemudian : pk+1 = pk+ 2∆y 
6. Apabila Sebaliknya,maka titik berikutnya bernilai (xk+1,yk+1), lalu perhitungannya: pk+1 = pk+ 2∆y- 2∆x 
7. Ulangi langkah 4 sebanyak ∆x kali.

Midpoint Circle

Algoritma Lingkaran Midpoint juga disebut algoritma lingkaran Bressenham. Bresenham mengembangkan generator lingkaran yang cukup efisien. 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 Circle Points untuk menampilkan titik dari seluruh lingkaran.

Langkah- langkah untuk membentuk lingkaran algoritma circle midpoint:

1. Tentukan radius r dengan titik pusat lingkaran(xc,yc) kemudian diperoleh (x0,y0) = (0,r)

2. Hitung nilai dari parameter P0 = 5/4 – r

3. Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut: Bila Pk < 0, maka titik selanjutnya adalah (xk+1 ,yk ) dan Parameter selanjutnya Pk+1 =Pk + 2xk+1 + 1 Bila tidak Pk > 0, maka selanjutnya adalah (xk+1 ,yk-1 )dan Parameter selanjutnya Pk+1=Pk + 2xk+1 + 1 – 2yk+1 Dimana 2xk+1 = 2xk + 2 dan 2yk+1 = 2yk – 2

4. Tentukan titik simetris pada ketujuh oktan yang lain

5. Gerakkan setiap posisi pixel(x,y) pada garis melingkar dari lingkaran dengan titik pusat (xc,yc) dan tentukan nilai koordinat: Xk+1 = xk + 1 dan Yk+1 = yk , atau Yk+1 = yk -1

6. Ulangi langkah ke3 sampai 5, sehingga X >= y