Algoritma Pembentukan Garis
Algoritma Pembentukan Garis
Garis dibuat dengan menentukan dua endpoint atau posisi titik awal dan akhir dari suatugaris. Kemudian peralatan output membuat garis sesuai posisi titiktitik tersebut. Untuk peralatananalog seperti plotter dan random-scan display garis lurus dapa dihasilkan dengan halus.Pada peralatan digital garis lurus dihasilkan dengan menetapkan titik diskrit antara titik awal dan akhir. Posisi titik diskrit sepanjang garis lurus data diperhitungkan dari persamaan garistersebut.Untuk menentukan nilai suatu titik, dapatdigunakan prosedur dasar dimana x sebagai nilaikolom pixel dan y sebagai nilai scanline sebagaiberikut :
setPixel(x,y)
bila nilai x dan y sudah tersimpan padaframe bufferuntuk dapat menampilkannyapada layermenggunakan fungsi dasar
getPixel(x,y)
1. Algoritma Digital Differential Analyzer (DDA)
Algoritma Digital Differential Analyzer (DDA) adalah algoritma pembentukangarisberdasarkan perhitungan dx maupun dy dengan menggunakan rumus dy = m.dx.Garis dibuatdengan menentukan dua endpoint yaitu titik awal dan titik akhir. Setiapkoordinat titik yangmembentuk garis diperoleh dari perhitungan kemudian dikonversikanmenjadi nilai integer.
Algoritma pembentukan garis DDA:
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu titik sebagai awal(x0,y0) dan titik akhir(x1,y1).
3. Hitung dx=x1x0, dan dy= y1y0.
4. Tentukan langkah, yaitu dengan cara jarak maksimum jumlah penambahan nilai xmaupun nilai y, dengan cara :*Bila nilai absolut dari dx lebih besar dari absolut dy, maka langkah= absolut dari dx.*Bila tidak maka langkah= absolut dari dy
5. Hitung penambahan koordinat pixel yaitu x_increment=dx/langkah, dany_increment=dy/langkah
6. Koordinat selanjutnya (x+x_increment, y+y_increment)
7. Posisi pixel pada layar ditentukan dengan pembulatan nilai koordinat tersebut.
8. Ulangi nomor 6 dan 7 untuk menentukan posisi pixel selanjutnya,sampai x=x1dan y=y1.
Algoritma Bressenham
Tujuan dari algoritma Bressenham ini adalah untuk menghindari pembulatan nilai seperti pada algoritma
DDA
Pada algoritma bressenham, nilai y kedua dan seterusnya, dihitung dari nilai ysebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikanalgoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnyadilakukan dengan cara menghilangkan operasi bilangan riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.
Langkah-langkah Algoritma Bressenham :
a. Langkah-langkah Algoritma Bressenham (Dx>Dy)
1. Tentukan 2 titik yang akan dihubungkan dalam pembentukan garis
2. Tentukan salah satu titik disebelah kiri sebagai titik awal, yaitu (X0, Y0) dan titik lainnyasebagai titik akhir (X1, Y1).
3. Hitung Dx=x2-x1, Dy=y2-y1, d1=2*DX dan d2=2*Dy - 2*Dx, e=d1-dx, x=x1, y=y1
4. Gambar pixel di (x,y)
5. Untuk setiap e>=0 hitung e=e+d2 dan y=y+1 Jika tidak hitung e=e+d1 dan y=y
6. Hitung x=x+17. Jika x>=x2 stop, jika tidak kembali ke langkah 4
b. Langkah-langkah Algoritma Bressenham (Dx<Dy)
1. Tentukan 2 titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu titik disebelah kiri sebagai titik awal, yaitu (X0, Y0) dan titik lainnyasebagai titik akhir (X1, Y1)
3. Hitung Dx=x2-x1, Dy=y2-y1, d1=2*Dy dan d2=2*Dy - 2*Dx, e=d1-dy, x=x1, y=y1
4. Gambar pixel di (x,y)
5. Untuk setiap e>=0 hitung e=e+d2 dan x=x+1 Jika tidak hitung e=e+d1 dan x=x
6. Hitung y=y+1. Jika y>=y2 stop, jika tidak kembali ke langkah 4
Garis dibuat dengan menentukan dua endpoint atau posisi titik awal dan akhir dari suatugaris. Kemudian peralatan output membuat garis sesuai posisi titiktitik tersebut. Untuk peralatananalog seperti plotter dan random-scan display garis lurus dapa dihasilkan dengan halus.Pada peralatan digital garis lurus dihasilkan dengan menetapkan titik diskrit antara titik awal dan akhir. Posisi titik diskrit sepanjang garis lurus data diperhitungkan dari persamaan garistersebut.Untuk menentukan nilai suatu titik, dapatdigunakan prosedur dasar dimana x sebagai nilaikolom pixel dan y sebagai nilai scanline sebagaiberikut :
setPixel(x,y)
bila nilai x dan y sudah tersimpan padaframe bufferuntuk dapat menampilkannyapada layermenggunakan fungsi dasar
getPixel(x,y)
1. Algoritma Digital Differential Analyzer (DDA)
Algoritma Digital Differential Analyzer (DDA) adalah algoritma pembentukangarisberdasarkan perhitungan dx maupun dy dengan menggunakan rumus dy = m.dx.Garis dibuatdengan menentukan dua endpoint yaitu titik awal dan titik akhir. Setiapkoordinat titik yangmembentuk garis diperoleh dari perhitungan kemudian dikonversikanmenjadi nilai integer.
Algoritma pembentukan garis DDA:
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu titik sebagai awal(x0,y0) dan titik akhir(x1,y1).
3. Hitung dx=x1x0, dan dy= y1y0.
4. Tentukan langkah, yaitu dengan cara jarak maksimum jumlah penambahan nilai xmaupun nilai y, dengan cara :*Bila nilai absolut dari dx lebih besar dari absolut dy, maka langkah= absolut dari dx.*Bila tidak maka langkah= absolut dari dy
5. Hitung penambahan koordinat pixel yaitu x_increment=dx/langkah, dany_increment=dy/langkah
6. Koordinat selanjutnya (x+x_increment, y+y_increment)
7. Posisi pixel pada layar ditentukan dengan pembulatan nilai koordinat tersebut.
8. Ulangi nomor 6 dan 7 untuk menentukan posisi pixel selanjutnya,sampai x=x1dan y=y1.
Algoritma Bressenham
Tujuan dari algoritma Bressenham ini adalah untuk menghindari pembulatan nilai seperti pada algoritma
DDA
Pada algoritma bressenham, nilai y kedua dan seterusnya, dihitung dari nilai ysebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikanalgoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnyadilakukan dengan cara menghilangkan operasi bilangan riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.
Langkah-langkah Algoritma Bressenham :
a. Langkah-langkah Algoritma Bressenham (Dx>Dy)
1. Tentukan 2 titik yang akan dihubungkan dalam pembentukan garis
2. Tentukan salah satu titik disebelah kiri sebagai titik awal, yaitu (X0, Y0) dan titik lainnyasebagai titik akhir (X1, Y1).
3. Hitung Dx=x2-x1, Dy=y2-y1, d1=2*DX dan d2=2*Dy - 2*Dx, e=d1-dx, x=x1, y=y1
4. Gambar pixel di (x,y)
5. Untuk setiap e>=0 hitung e=e+d2 dan y=y+1 Jika tidak hitung e=e+d1 dan y=y
6. Hitung x=x+17. Jika x>=x2 stop, jika tidak kembali ke langkah 4
b. Langkah-langkah Algoritma Bressenham (Dx<Dy)
1. Tentukan 2 titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu titik disebelah kiri sebagai titik awal, yaitu (X0, Y0) dan titik lainnyasebagai titik akhir (X1, Y1)
3. Hitung Dx=x2-x1, Dy=y2-y1, d1=2*Dy dan d2=2*Dy - 2*Dx, e=d1-dy, x=x1, y=y1
4. Gambar pixel di (x,y)
5. Untuk setiap e>=0 hitung e=e+d2 dan x=x+1 Jika tidak hitung e=e+d1 dan x=x
6. Hitung y=y+1. Jika y>=y2 stop, jika tidak kembali ke langkah 4
Comments
Post a Comment