Algoritma DDA, Bressenham, dan Midpoint Circle

DDA (Digital Differential Analyzer)

Algoritma DDA (Digital Differential Analyzer), adalah algoritma pembentukan garis yang menggunakan rumus dy = m.dx berdasarkan perhitungan dari dx dan juga dy. Garis yang terbentuk melalui titik koordinat diperoleh dari perhitungan yang kemudian di konversikan menjadi integer. Algoritma DDA merupakan garis yang membentak diantara 2 titik, yaitu P1 dan P2. Bentuk sudut dari kedua titik tersebut membentuk sudut yang besarnya beragam. Garis lurus yang membentang turunan dari x dan y merupakan konstanta. 

Beberapa 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.

Bressenham.

    Algoritma Garis Bressenham, merupakan algoritma yang menentukan dimana titik-titik dalam raster n-dimensi harus ditempatkan untuk membentuk garis lurus antara duatitik yang diberikan. Hal ini biasanya digunakan untuk menggambar garis pada layarkomputer, karena hanya menggunakan integer penambahan, pengurangan dan pergeseran bit, yang mana semua itu merupakan proses yang sangat murah dalam arsitektur computer yang standar. Algoritma ini adalah algoritma yang paling awal dikembangkan di bidang grafika komputer. Algoritma ini juga dapat membentuk lingkaran dengan sedikit penambahan pada algoritma-nya.

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