Membuat
Garis Dengan Metode DDA Dan Bressenham Dengan Pemrograman Pascal
Ada beberapa metode pembentuk garis yang umum
digunakan yaitu:
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.
Berikut ini adalah algoritma DDA :
1. Tentukan
2 buah titik.
2. Tentukan
yang menjadi titik awal (X0,Y0) dan titik akhir (X1,Y1).
3. Hitung
Dx dan DyDx = X1-X0 dan Dy
= Y1 – Y0
4. Bandingkan
Abs(Dx) dan Abs(Dy)Jika Abs(Dx) > Abs(Dy)
makaSteps = Abs(Dx) bila tidak Steps = Abs(Dy)
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 = X1, Y = Y1
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)
Dx = (X1-X0)
(17-10) = 7
Dy = (Y1-Y0)
(16-10) = 6
Abs(Dx) = Abs(7) = 7
Abs(Dy) = Abs(6) = 6
Abs(Dx) > Abs(Dy) maka
Step = Abs(Dx) = 7
Xincrement = Dx / Steps. 7 / 7 = 1
Yincrement = Dy / Steps. 6 / 7 = 0,86
Tabel 3.1. 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
|
B. ALGORITMA
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 (x0,y0) dan titik lainnya
sebgai titik akhir (x1,y1).
3.
Hitung dx,dy,2dx
dan 2dy-2dx.
4.
Hitung parameter P0 = 2dy-dx
5.
Untuk setiap Xk sepanjang
jalur garis, dimulai dengan k=0,bila pk <0,>k+1, yk),
dan Pk+1 = Pk+2dybila tidak, maka titik
selanjutnya adalah (xk+1,yk+1), dan Pk+1 = Pk+2dy-2dx
6.
Ulangi langkah no 5 untuk menentukan
posisi pixel selanjutnya, sampai x = x1 dan y = y1.
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 = x1 dan y = y1
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
|