PENGERTIAN ALGORITMA DDA, BESERTA SOAL DAN JAWABANNYA

PENGERTIAN ALGORITMA DDA ( Digital Diferential Analyzer)

DDA adalah algoritma pembentuk garis yang didasarkan pada perasamaan (2-8). Garis dibuat menggunakan titik awal (x1, y1) dan titik akhir (x2, y2). Setiap koordinat titik (xk, yk) yang membentuk garis diperoleh dari perhitungan, kemudian hasil perhitungan dikonversikan menjadi nilai integer. Algoritma ini bisa digunakan untuk menghitung garis dengan semua kemiringan. { 0 < m < 1 ; m>1 ; −1 < m < 0 ; m < −1 }.

Berikut adalah langkah-langkah pembentukan garis berdasarkan algoritma DDA:
1.   Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2.   Tentukan salah satunya sebagai titik awal (x1, y1) dan yang lain sebagai titik akhir (x2, y2).
3.   Hitung : dx =  x2 − x1  dan  dy = y2 − y1.
4.   Tentukan step, dengan ketentuan berikut:      
-  bila  |dx| > |dy|   maka  step = |dx|.
- bila tidak, maka step = |dy|.
5.   Hitung penambahan koordinat piksel dengan persamaan:           

x_inc = dx / step             

y_inc = dy / step.

6.   Koordinat selanjutnya :   

x = x + x_inc    y = y + y_inc.

7.   Lakukan pembulatan u = Round(x), v = Round(x), kemudian plot piksel (u, v) pada layar
8. Ulangi point 6 dan 7 untuk menentukan posisi piksel berikutnya sampai x = x2  dan  y = y2.

CONTOH SOAL

Soal

Diketahui 2 buah titik A(2,1) dan titik B(8,5) bila titik A sebagai titik awal dan titik B sebagai titik akhir, maka buatlah garis yang menghubungkan titik tersebut dengan menggunakan algoritma DDA.

Jawaban

Titik awal (x1, y1) = A(2,1) dan Titik akhir (x2, y2) = B(8,5)

dx = x2 − x1 = 8 −2 = 6   dan  dy = y2 − y1 = 5 − 1 = 4  

Karena: |dx| >  |dy|, maka step = |dx| = 6

x_inc = dx / step =  6/6 = 1 y_inc = dy / step =  4/6 = 0,67

*Iterasi ke-1: (x,y) = (2,1)

 x+x_inc = 2 + 1 = 3

 y+y_inc = 1 + 0,67 = 1,67

Koordinat selanjutnya : (x,y) = (3;  1,67)

Pembulatan (3;  1,67) ≈ (3,2). Gambar titik (3,2) dilayar.

*Iterasi ke-2: (x,y) = (3;  1,67)

x+x_inc = 3 + 1 = 4

 y+y_inc = 1,67 + 0,67 = 2,34

Koordinat selanjutnya : (x,y) = (4;  2,34)

Pembulatan (4;  2,34) ≈ (4,2). Gambar titik (4,2) dilayar.

*Iterasi ke-3: (x,y) = (4;  2,34)

xA+x_inc = 4 + 1 = 5

yA+y_inc = 2,34 + 0,67= 3,01

Koordinat selanjutnya : (x,y) = (5;   3,01)

Pembulatan (5;   3,01) ≈ (5,3). Gambar titik (5,3) dilayar.

*Iterasi ke-4: (x,y) = (5;  3,01)

xA+x_inc = 5 + 1 = 6

yA+y_inc = 3,01 + 0,67 = 3,68 

Koordinat selanjutnya : (x,y) = (6;   3,68)

Pembulatan (6;   3,68) ≈ (6,4). Gambar titik (6,4) dilayar.

*Iterasi ke-5: (x,y) = (6;  3,68)

xA+x_inc = 6 + 1 = 7

yA+y_inc = 3,68 + 0,67 = 4,35 

Koordinat selanjutnya : (x,y) = (7;   4,35)

Pembulatan (7;   4,35) ≈ (7,4). Gambar titik (7,4) dilayar.

*Iterasi ke-6: (x,y) = (7;  4,35)

 xA+x_inc = 7 + 1 = 8  

yA+y_inc = 4,35 + 0,67 = 5,02 

Koordinat selanjutnya : (x,y) = (8;   5,02)

Pembulatan (8;   5,02) ≈ (8,5). Gambar titik (8,5) dilayar.

Karena x = x2 = 8, maka iterasi dihentikan, sehingga diperoleh titik-titik pembentuk garis sebagai berikut: (2,1), (3,2), (4,2), (5,3), (6,4), (7,4) dan (8,5).