Definisi dan Cara Kerja DDA, Bresenham, dan Midpoint Circle

 DDA (Digital Differential Analyzer)

Merupakan langkah-langkah untuk menyelesaikan masalah secara berurutan. Ada banyak model algoritma yang bisa diterapkan dalam menyelesaikan beberapa pekerjaan. Salah satunya adalah algoritma DDA atau yang biasa disingkat Digital Differential Analyzer.

Algoritma DDA 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.

Langkah-Langkah Pembentukan Garis Algoritma DDA

Ada beberapa langkah untuk pembentukan garis algoritma DDA, antara lain :

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.

Contoh:

Algoritma Bresenhem

Algoritma bresenham merupakan suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). Bagian pengkonversian (scan-knversi) garis akan melakukan kalkulasi untuk penambahan nilai-nilai integer (yang dibutuhkan untuk membentuk garis) yang disesuaikan dengan tipe grafik yang dipakai oleh layar komputer (keadaan monitor pc) kita. 

Untuk mengilustrasikan pendekatan bresenham, pertama kita harus memperhatikan proses scan- konvensi untuk garis dengan slope positif yang lebih kecil dari 1. Posisi pixel sepanjang line-path kemudian ditentukan dengan penyamplingan pada unit interval x.dimulai dari endpoint kiri (Xo,Yo) dari garis yang diberikan, kita pindahkan beberapa kolom berturut-turut (berdasarkan posisi x) dan plot pixel-pixel yang mempunyai nilai scan-line y ke jarak yang paling dekat dengan line-path.

Langkah-langkahnya

1. Tentukan titik awal dan akhir
   Titik awal (X1,Y1)
   Titik akhir (X2, Y2)
2. Tentukan Nilai pengubahan posisi (P)
   DX = X2 - X1
   DY = Y2 - Y1
   P (Awal) = 2 * DY - DX
   Jika P < 0 maka X = X + 1, Nilai Y Tetap
   (P) Selanjutnya adalah P = P + (2 * DY)
   Jika tidak maka X = X + 1, Y = Y + 1
   (P) Selanjutnya adalah P = P + 2 * (DY - DX)
3. Perulangan
   rumus yang di pakai dalam perulangan tergantung kondisi (P) apakah P > 0, P< 0.
   setelah itu gunakan rumus sesuai kondisi (P)

Ilustrasi:

Algoritma Midpoint Circle

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 (1 oktan), kemudian menggunakan CirclePoints untuk menampilkan titik dari seluruh lingkaran.

Fungsinya :

• Untuk mengatasi masalah yang timbul dari penerapan koordinat polar maupun rectangular, Bresenham menyusun suatu algoritma pembentukan lingkaran yang hanya menggunakan aritmetika integer. Secara prinsip algoritma ini sejenis dengan algoritma penggambaran garis yang disusun oleh orang yang sama.
• Lingkaran merupakan objek yang simetris sehingga karakteristik ini dapat dimanfaatkan untuk mengurangi pekerjaan pada saat menggambar lingkaran. Lingkaran dibagi menjadi 8 oktan (lihat

gambar 3.x), misalkan kita menyusun algoritma untuk menggambarkan lingkaran di oktan pertama, maka koordinat untuk 7 oktan selanjutnya dapat ditentukan.

Langkahnya :

1. Tentukan radius r dengan titk pusat lingkaran(xcenter,ycenter) kemudian diperoleh titik awal (x,r)
2. Hitung nilai parameter P0=1-r
3. Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut:
4. Bila Pk< 0, maka titik selanjutnya adalah (xk+1,yk), dan Pk+1=Pk+(2*xk+1)+1
5. Bila tidak, maka titik selanjutnya adalah (xk+1,yk­-1), dan Pk+1=Pk+(2*xk+1)+1­
6. Tentukan titik simetris pada ketujuh oktan yang lain
7. Ulangi langkah 3 dan 4, sampai nilai x>=y