Pengertian Algoritma
Menurut kamus besar bahasa indonesia terbitan balai pustaka tahun 1988, “algoritma adalah urutan logis pengambilan putusan untuk pemecahan masalah”. Menurut Microsoft Book-shelf, “algoritma adalah urutan langkah berhingga untuk memecahkan masalah logika atau matematika”. Berdasarkan defenisi-defenisi tersebut maka dapat disimpulkan, “algoritma adalah urutan langkah-langkah logis yang berhingga yang digunakan untuk memecahkan masalah”. Langkah-langkah di dalam algoritma harus logis, ini berarti hasil dari urutan langkah- langkah tersebut harus dapat ditentukan, benar atau salah. Langkah-langkah yang tidak benar dapat memberikan hasil yang salah. Menurut Donald E. Knuth dalam bukunya yang berjudul “the art of computer programming”.
ALGORITMA DDA
Digital Differential Analyzer (DDA)
adalah algoritma pembentukan garis
berdasarkan perhitungan dx maupun dy. Garis
dibuat dengan menentukan dua endpoint, yaitu
titik awal dan titik akhir. Setiap koordinat titik
yang membentuk garis diperoleh dari
perhitungan, kemudian dikonversikan menjadi
nilai integer. Prinsip dari Algoritma Digital
Differential Analyzer (DDA) adalah
mengambil nilai integer terdekat dengan jalur
garis berdasarkan atas sebuah titik yang telah
ditentukan sebelumnya (titik awal garis).
langkah-langkah :
⦁ Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
⦁ Tentukan salah satu titik sebagai awal(x0,y0) dan titik akhir(x1,y1).
⦁ Hitung dx=x1x0, dan dy= y1y0.
⦁ 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
⦁ Hitung penambahan koordinat pixel yaitu x_increment=dx/langkah, dany_increment=dy/langkah
⦁ Koordinat selanjutnya (x+x_increment, y+y_increment)
⦁ Posisi pixel pada layar ditentukan dengan pembulatan nilai koordinat tersebut.
⦁ Ulangi nomor 6 dan 7 untuk menentukan posisi pixel selanjutnya,sampai x=x1dan y=y1.
Algoritma DDA merupakan salah satu algoritma menggambar cukup sederhana
Bentuk garis:
⦁ Cenderung mendatar
Pixel bertambah 1 pada sumbu x dan bertambah
sebesar m pixel pada sumbu y
⦁ Cenderung tegak
Pixel bertambah 1 pada sumbu y dan bertambah
sebesar 1/m pixel pada sumbu x
⦁ Miring
Pixel bertambah 1 pada sumbu x dan bertambah
sebesar 1 pixel pada sumbu y
Contoh Algoritma DDA
Int dx = x2-x1;
Int dy = y2-y1;
Int steps,k,x1,y1,x2,y2;
Float x_inc, y_inc;
Float x = x1;
Float y = y1;
If (abs(dx)>abs(dy)) steps = abs(dx) else steps = abs(dy);
X_inc = dx/(float)steps;
Y_inc = dy/(float)steps;
setPixel(Round(x),Round(y));
Contoh hasil dari implementasi program yang menggunakan algoritma DDA dengan bahasa pemrograman java
Contoh hasil dari implementasi program yang menggunakan algoritma DDA dengan bahasa pemrograman java
Keuntungan dan Kerugian Algoritma DDA
Keuntungan dari algoritma Digital Differential Analyzer (DDA) adalah tidak perlu menghitung koordinat berdasarkan persamaan yang lengkap (menggunakan metode off set)
Kerugiannya dari algoritma Digital Differential Analyzer (DDA) adalah adanya akumulasi Round-off errors, sehingga garis akan melenceng dari garis lurus, selain itu operasi round-off juga menghabiskan waktu.
Algoritma pembentukan garis Bresenham
Algoritma Bressenham merupakan algoritma pembenrukan garis berdasarkan selisihantara gratis yang diinginkan terhadap setengah ukuran dari pixel yang sedang digunakan.Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungankoordinat piksel yang menggunakan persamaan, dengan cara menggantikan operasi bilangan rii perkalian dengan operasi penjumlahan, yang kemudian dikenal dengan AlgoritmaBresenham. Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai ysebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap.Perbaikan algoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan.Perbaikan berikutnya dilakukan dengan cara menghilangkan operasi bilangan riel denganoperasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan denganoperasi bilangan riel, terutama pada penambahan dan pengurangan.
Langkah-langkah pembentukan garis berdasarkan algoritma Bressenham adalah:
1. Tentukan dua titik yang akan dihubungkan dalam pembentukan garis.
2. Tentukan salah satu sebagai titik awal (x0, y0) dan titik akhir (x1, y1).
3. Hitung dx, dy, 2dy dan 2dy - 2dx
4. Hitung parameter : po = 2dy - dx
5. Untuk setiap xk sepanjang jalur garis, dimulai dengan k=0
- bila pk < 0 maka titik selanjutnya adalah:
(xk+1, yk) dan pk+1 = pk + 2dy
- bila tidak, titik selanjutnya adalah:
(xk+1, yk+1) dan pk+1 = pk + 2dy – 2dx
6. Ulangi nomor 5 untuk menentukan posisi pixel berikutnya, sampai
x = x1 atau y = y1.
Contoh hasil dari implementasi program yang menggunakan algoritma Bresenham dengan bahasa pemrograman java
Algoritma Midpoint Circle
Algoritma yang digunakan membentuk semua titik berdasarkan titik pusat dengan penambahan semua jalur sekeliling lingkaran. Algoritma ini diturunkan dari algoritma Midpoint untuk pembentukan garis. Dalam hal ini hanya diperhatikan bagian 45° dari suatu lingkaran (1 oktan), kemudian menggunakan CirclePoints untuk menampilkan titik dari seluruh lingkaran.
Tentukan radius r dengan titk pusat lingkaran(xcenter,ycenter) kemudian diperoleh titik awal (x,r)
Hitung nilai parameter P0=1-r
Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut:
Bila Pk< 0, maka titik selanjutnya adalah (xk+1,yk), dan Pk+1=Pk+(2*xk+1)+1
Bila tidak, maka titik selanjutnya adalah (xk+1,yk-1), dan Pk+1=Pk+(2*xk+1)+1
Tentukan titik simetris pada ketujuh oktan yang lain
Ulangi langkah 3 dan 4, sampai nilai x>=y
Komentar
Posting Komentar