Grafik Kom & Pengolahan Citra

ALGORITMA GARIS

Algoritma garis adalah algoritma untuk menentukan lokasi pixel yang paling dekat dengan garis sebenarnya. Ada beberapa algoritma untuk menggambar garis, salah satunya yaitu:

Algoritma  Digital  Differential  Analyzer  (DDA)  adalah  algoritma  pembentukan  garis  berdasarkan  perhitungan  dx maupun  dy  dengan menggunakan  rumus  dy  = m.dx.  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.

Keuntungan  dari  algoritma  ini  adalah  tidak  perlu  menghitung  koordinat  berdasarkan  persamaan  yang  lengkap  (menggunakan  metode  offset).  Sedangkan  kerugiannya adalah adanya akumulasi Round-off errors,  sehingga garis akan melenceng  dari garis lurus, selain itu operasi round-off juga menghabiskan waktu.

DDA adalah algoritma pembentukan garis berdasarkan perhitungan x dan y, menggunakan rumus y = m. x. 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. Langkah-langkah pembentukan menurut algoritma DDA, yaitu :

1. Tentukan dua titik yang akan dihubungkan.
2. Tentukan salah satu titik sebagai titik awal (x0, y0) dan titik akhir (x1, y1).
3. Hitung x = x1 - x0 dan y = y1 - y0. 4.
    Tentukan step, yaitu jarak maksimum jumlah penambahan nilai x maupun nilai y dengan cara :
    bila nilai | y| > | x| maka step = nilai | y|. bila tidak maka step = | x|.
5. Hitung penambahan koordinat pixel yaitu x_increment = x / step dan y_increment = y / step.
6. Koordinat selanjutnya (x+x_incerement, y+y_increment).
7. Posisi pixel pada layer ditentukan dengan pembulatan nilai koordinasi tersebut.
8. Ulangi step 6 dan 7 untuk menentukan posisi pixel selanjutnya, sampai x = x1 dan y = y

Untuk menggambarkan algoritma DDA dalam pembentukan suatu garis yang menghubungkan titik (10,10) dan (17,16), pertama-tama ditentukan dx dan dy, kemudian dicari step untuk mendapatkan x_increment dan y_increment.

deltax = x1 - x0 = 17-10 = 7

deltay = y1 - y0 = 16 -10 = 6

selanjutnya hitung dan bandingkan nilai  absolutnya.

|deltax| = 7 

|deltay| = 6

karena |deltax| > |deltay|, maka step = |deltax| = 7, maka diperoleh :

x_inc = 7/7= 1

y_inc = 6/7 = 0,86

Setelah kita mengetahui teori Algoritma garis DDA langsung saja kita praktekkan ke program.

 

Implementasi Membuat garis dengan DDA adalah sebagai berikut.

Hasilnya akan tampak seperti gambar berikut :