Assalamualaikum..
Salam sejahtera.. baik kali ini saya akan sharing materi tentang Algoritma Pembentuk Garis. Namun sebelum itu kita harus tahu dulu apa itu garis ? Nah, menurut Wikipedia Bahasa Indonesia:
Garis (bahasa Inggris: line), dalam geometri Euklides, adalah sebuah lengkungan lurus. Ketika geometri digunakan untuk memodel dunia nyata, garis digunakan untuk menggambarkan objek lurus dengan lebar dan tinggi yang berbeda. Garis adalah idealisasi dari objek semacam itu dan tidak punya lebar atau tinggi dan panjangnya dianggap tak hingga
Dalam geometri, sebuah garis biasanya merupakan satu anggapan primitif dari sistem aksioma. Garis terdiri darihimpunan titik dan merupakan subhimpunan dari bidang. Dalam geometri diferensial, konsep garis digeneralisasikan menjadi geodesi. Dalam geometri sintetis, sebuah garis adalah satu anggapan lama dalam sistem Euklides, Karl von Staudt, dan David Hilbert. Sebuah garis adalah sebutan terdefinisikan dalam sistemGiuseppe Peano, Mario Pieri dan Alessandro Padoa.
Sebuah ruas garis adalah bagian dari garis yang dikelilingi oleh dua ujung berbeda dan terdiri dari setiap titik di garis antara kedua ujungnya. Tergantung cara ruas garis ini dideginisikan, satu dari dua ujung tersebut bisa jadi atau bukan bagian dari ruas garis. Dua ruas garis atau lebih bisa memiliki hubungan yang sama seperti garis, seperti paralel, perpotongan, atau kemiringan.
Sudah tahu kan pengertian garis ? klo gitu kita langsung saja nih bahas Algoritma Pembentuk Garisnya .
ALGORITMA PEMBENTUK GARIS
Ada beberapa metode pembentuk garis
yang umum digunakan yaitu Algoritma DDA (Digital Defferential Analyzer) dan Algoritma
Bressenham.
11.
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
(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
|
2.
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
|
Makasih sudah berkunjung. Semoga bermanfaat ! :)
