Algoritma DDA (Digital Defferential Analyzer) dan Algoritma Bressenham

DDA (Digital Defferential Analyzer)

Garis merupakan kumpulan dari titik-titik, untuk membentuk garis lurus adalah dengan mengetahui titik awal dan titik akhir. Dengan mengetahui titik awal dan titik akhir maka kita dapat membentuk garis. Untuk menggambarkan proses pembuatan garis dari titik awal ke titik akhir ada berbagai algoritma. Algoritam yang umum adalah DDA dan Bresenham.

Berikur ini adalah algoritma DDA

1. Tentukan 2 buah titik.

2. Tentukan yang menjadi titik awal (X₀,Y₀) dan titik akhir (X₁,Y₁).

3. Hitung Dx dan D_yD_x = X₁-X₀ dan D_y = Y₁ – Y₀

4. Bandingkan Abs(D_x) dan Abs(D_y)Jika Abs(D_x) > Abs(D_y) makaSteps = Abs(D_x) bila tidak Steps = Abs(D_y)

5. Hitung penambahan koordinat pixel, yaitu:X_increment = dx/steps, danY_increment = dy/steps.

6. Koordint selanjutnya, yaituX+X_incrementY+Y_increment

7. Posisi pixel ditentukan dengan pembulatan nilai koordinat tersebut.

8. Ulangi langkah 6 dan 7 untuk posisi selanjutnya sampai X = X₁, Y = Y₁

DDA (bahasa pascal)Procedure DDA;

Begin

Write(‘Masukkan Nilai X0 : ‘);

Readln(X0); Write(‘Masukkan Nilai Y0 : ‘);

Readln(Y0); Write(‘Masukkan Nilai X1 : ‘);

Readln(X1); Write(‘Masukkan Nilai Y1 : ‘);

Readln(Y1);

Dx:= X1-X0;

Dy:= Y1-Y0;

If Abs(Dx) > Abs(Dy) Then

Steps:= Abs(Dx)

Else

Steps:= Abs(Dy);

Endif

PutPixel(x,y,Hitam);

For x = 1 to Steps Do

X := X + Xincrement;

Y := Y + Yincrement;

PutPixel(x,y,Hitam);

End;

End;

Contoh :

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

Jawab

Titik Awal = A(10,10)

Titik Akhir = B(17,16)

D_x = (X₁-X₀) (17-10) = 7

D_y = (Y₁-Y₀) (16-10) = 6

Abs(D_x) = Abs(7) = 7

Abs(D_y) = Abs(6) = 6

Abs(D_x) > Abs(D_y) maka

Step = Abs(D_x) = 7

Xincrement = Dx / Steps. 7 / 7 = 1

Yincrement = Dy / Steps. 6 / 7 = 0,86

                Nilai perhitungan

K	X	Y	Xinc	Yinc
-	-	-	10	10
0	11	10,86	11	11
1	12	11,71	12	12
2	13	12,57	13	13
3	14	13,43	14	14
4	15	14,28	15	15
5	16	15,14	16	16
6	17	16	17	16

BRESSENHAMALGORITMA BRESSENHAM

Tujuan dari algoritma Bressenham ini adalah untuk menghindari pembulatan nilai seperti pada algoritma DDA.

1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.

2. Tentukan salah satu titik di sebelah kiri sebagai titi awal, yaitu (x₀,y₀) dan titik lainnya sebgai titik akhir (x₁,y₁).

3. Hitung d_x,d_y,2_dx dan 2_dy-2_dx.

4. Hitung parameter P₀ = 2_dy-d_x

5. Untuk setiap X_k sepanjang jalur garis, dimulai dengan k=0,bila p_k <0,>k+1, y_k), dan P_k+1 = P_k+2_dybila tidak, maka titik selanjutnya adalah (x_k+1,y_k+1), dan P_k+1 = P_k+2_dy-2_dx

6. Ulangi langkah no 5 untuk menentukan posisi pixel selanjutnya, sampai x = x₁ dan y = y₁.

Sub Rutim Berssenham dalam CVoid line (int xa, ya, xb, yb, xEnd; flot x,y)

{

Int dx = abs(xb-xa), dy=abs(yb-ya);

Int p = 2*dy-dx;

Int twoDy = 2*dy,

twodyDx = 2*(dy-dx);

If (xa>xb)

{

X = xb;

Y = yb;

Xend = xa;

}

Else

{

X = xa;

Y = ya;

xEnd = xb;

}

SetPixel(x,y);

While (x

{

X++;

If (p<0)

P+ = twody;

Else

{

Y++;

P+ = twoDyDx;

}

SetPixel(x,y);

}

};

Contoh :

Berdasarkan contoh pada algoritma DDA buatlah dengan metode bresenham.

JAWAB

dx = abs(xb – xa)= abs(17 – 10 ) = 7

dy = abs(yb – ya)= abs(16 – 10) = 6

p = 2 * dy - dx = 2 * 6 – 7 = 5

twody = 2 * dy = 2 * 6 = 12

twodydx= 2 * (dy – dx ) = 2 * ( 6 – 7 ) = -2

Periksa xa dan xb

xa = 10 < xb =" 17Maka">

x = xa = 10

y = ya = 10

Xend = xa = 17

Ulangi selama x <>

K0: x = x + 1 = 10 + 1 = 11

Periksa nilai p , dimana p = 5

y = y + 1 = 10 + 1 = 11

p = p + twodydx = 5 + (-2) = 3

K1: x = x + 1 = 11 + 1 = 12

Periksa nilai p, dimana p = 3

y = y +1 = 11 + 1 = 12

p = p + twodydx = 3 + (-2) = 1

K2: x = x + 1 = 12 + 1 = 13

Periksa nilai p, dimana p = 1

y = y +1 = 12 + 1 = 13

p = p + twodydx = 1 + (-2) = -1

K3: x = x + 1 = 13 + 1 = 14

Periksa nilai p, dimana p = -1 Nilai y tetap yaitu y=13

p = p + twody = (-1) + 12 = 11

K4: x = x + 1 = 14 + 1 = 15

Periksa nilai p, dimana p = 11

y = y +1 = 13 + 1 = 14

p = p + twodydx = 11 + (-2) = 9

K5: x = x + 1 = 15 + 1 = 16

Periksa nilai p, dimana p = 9

y = y +1 = 14 + 1 = 15

p = p + twodydx = 9 + (-2) = 7

K6: x = x + 1 = 16 + 1 = 17

Periksa nilai p, dimana p = 7 y = y +1 = 15 + 1 = 16

p = p + twodydx = 7 + (-2) = 5

Proses berhenti karena x = x₁ dan y = y₁

Masukkan nilai kedalam tabel, seperti pada tabel 3.2. Tabel 3.2.

Hasil penelusuran dengan bressenham

K	Pk	(Xk+1 , Yk+1)
-	-	10,10
0	3	11,11
1	1	12,12
2	-1	13,13
3	11	14,13
4	9	15,14
5	7	16,15
6	5	17,16