Definisi dan cara kerja dari DDA(Digital Diferential Analyzer), Bresenham, Midpoint Circle

• DDA(Digital Differential Analyzer)

DDA ( Digital Differential Analyzer) adalah garis yang membentang antara 2 titik, P1 dan P2. Dimana ke-2 titik ini membentuk sudut yang besarnya sangat bervariasi. Bekerja atas dasar penambahan nilai x dan nilai y. Dimana pada garis lurus, turunan pertama dari x dan y adalah kostanta. Algoritma DDA adalah algoritma pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus dy=m.dx. Semua koordinat titik yang membentuk garis diperoleh dari perhitungan kemudian dikonversikan menjadi nilai integer. 

Berikut langkah langkah untuk pembentukan garis algoritma DDA, yaitu

1. Pertama, dalam pembentukan garis tentukan dua titik yang akan dihubungkan terlebih dahulu.

2. Kemudian, tentukan titik awal dan titik akhir.

3. Hitung hasil perhitungan dari dx = x2 - x1 dan dy = y2 - y1.

4. Tentukan step, dengan syarat :

    • Jika dx > dy maka step = dx

    • Sebaliknya, jika dx < dy, maka step = dy

5. Hitung penambahan koordinat pixel dengan permasaan menggunakan :

    • x_inc = dx / step

    • y_inch = dy / step

6. Untuk koordinat selanjutnya yaitu x+x_inc, y+y_inch.

7. Hasil perhitungan nilai koordinat dibulatkan.

8. Untuk menentukan posisi pixel berikutnya, ikuti kembali langkah 6 dan 7.

• Bresenham

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

Berikut langkah langkah untuk pembentukan garis algoritma Bresenham, yaitu

1. Tentukan 2 titik yang akan dihubungkan dalam pembentuk garis.

2. Tentukan salah satu titik disebelah kiri sebagai titik awal, yaitu (X0,Y0) dan titik lainnya sebagai titik akhir (X1, Y1).

3. hitung Dx, Dy, 2DX dan 2Dy-2Dy.

4. Hitung parameter P0= 2Dy – 2Dx.

5. Untuk setiap X1 sepanjang jalur garis, dimulai dengan k=0,

• bila pk<0, makatitik selanjutnya adalah (Xk + 1, Yk) dan Pk+1 = Pk +2Dy
• bila tidak, maka titik selanjutnya adalah (Xk + 1, Yk +1) dan Pk+1 = Pk +2Dy – 2Dx.

6. Ulangi langkah no. 5 untuk menentukan posisi selanjutnya, sampai X=X1 dan Y=Y1

• Midpoint Circle

Berikut langkah langkah untuk pembentukan lingkaran algoritma Bresenham, yaitu

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