MEMBAHAS DEFINISI DAN CARA KERJA DARI DDA(DIGITAL DIFERENTIAL ANALYZER), BRESENHAM, MIDPOINT CIRCLE

ALGORITMA DIGITAL DIFFERENTIAL ANALYZER (DDA)

Apa itu Algoritma…? Algoritma merupakan langkah-langkah untuk menyelesaikan masalah secara berurutan. Ada banyak model algoritma yang bisa diterapkan dalam menyelesaikan beberapa pekerjaan. Salah satunya adalah algoritma DDA atau yang biasa disingkat Digital Differential Analyzer.

Algoritma DDA adalah algoritma pembentukan garis yang menggunakan rumus dy = m.dx berdasarkan perhitungan dari dx dan juga dy. Garis yang terbentuk melalui titik koordinat diperoleh dari perhitungan yang kemudian di konversikan menjadi integer.

Algoritma DDA merupakan garis yang membentak diantara 2 titik, yaitu P1 dan P2. Bentuk sudut dari kedua titik tersebut membentuk sudut yang besarnya beragam. Garis lurus yang membentang turunan dari x dan y merupakan konstanta.

Keuntungan utama dari DDA atas Differential analog konvensional analyzer adalah presisi yang lebih besar dari hasil dan kurangnya drift / noise / slip / lash dalam perhitungan. presisi ini hanya dibatasi oleh ukuran register dan hasil accumulated rounding, yang mengakibatkan kesalahan pemotongan / penambahan berulang.

Algoritma DDA merupakan garis yang membentak diantara 2 titik, yaitu P1 dan P2. Bentuk sudut dari kedua titik tersebut membentuk sudut yang besarnya beragam. Garis lurus yang membentang turunan dari x dan y merupakan konstanta.

Keuntungan utama dari DDA atas Differential analog konvensional analyzer adalah presisi yang lebih besar dari hasil dan kurangnya drift / noise / slip / lash dalam perhitungan. presisi ini hanya dibatasi oleh ukuran register dan hasil accumulated rounding, yang mengakibatkan kesalahan pemotongan / penambahan berulang.

Untuk masalah yang dapat dinyatakan sebagai persamaan diferensial, sebuah DDA dapat menyelesaikannya lebih cepat daripada general purpose computer  seperti personal computer (menggunakan teknologi serupa). Namun pemrograman ulang sebuah DDA untuk memecahkan masalah yang berbeda (atau memperbaiki bug) jauh lebih sulit daripada pemrograman pada general purpose computer . Banyak DDA yang dibuat untuk satu masalah saja dan tidak bisa diprogram ulang tanpa mendesain ulang DDA tersebut.

Langkah-Langkah Pembentukan Garis Algoritma DDA

Ada beberapa langkah untuk pembentukan garis algoritma DDA, antara lain :

1.     Pertama, dalam pembentukan garis tentukan dua titik yang akan dihubungkan terlebih dahulu.

2.     Kemudian, tentukan titik awal dan titik akhir.

3.     Hitung hasil perhitungan dari dx = x2 - x1 dan dy = y2 - y1.

4.     Tentukan step, dengan syarat :

·       Jika dx > dy maka step = dx

·       Sebaliknya, jika dx < dy, maka step = dy

5.     Hitung penambahan koordinat pixel dengan permasaan menggunakan :

·       x_inc = dx / step

·       y_inch = dy / step

6.     Untuk koordinat selanjutnya yaitu x+x_inc, y+y_inch.

7.     Hasil perhitungan nilai koordinat dibulatkan.

8.     Untuk menentukan posisi pixel berikutnya, ikuti kembali langkah 6 dan 7.

ALGORITMA BRESENHAM

Algoritma ini digunakan untuk pembentukan garis menggunakan bilangan integer, sehingga tidak diperlukan adanya proses pembulatan bilangan pada setiap iterasinya. Algoritma Bresenham ini juga dikenal dengan istilah Midpoint Line Algorithm (teknik ini juga digunakan pada penggambaran lingkaran).

Untuk menggambarkan piksel-piksel dalam garis lurus, parameter yang digunakan tergantung dari gradient, jika besarnya gradient diantara 0 dan 1, maka digunakan sumbu x sebagai parameter dan sumbu y sebagai hasil dari fungsi, sebaliknya, bila gradient melebihi 1, maka sumbu y digunakan sebagai parameter dan sumbu x sebagai hasil dari fungsi, hal ini bertujuan untuk menghindari terjadinya gaps karena adanya piksel yang terlewatkan. Hasil dari fungsi biasanya merupakan bilangan real, sedangkan koordinat pixel dinyatakan dalam bilangan integer (x,y), maka diperlukan operasi pembulatan kedalam bentuk integer terdekat. Penggambaran garis lurus dengan metode diatas dimulai dengan operasi bilangan real untuk menghitung gradient m dan konstanta c.

Pada proses pembentukan garis ini setiap titik dibuat melalui iterasi tanpa ada pembulatan dari hasil perhitungan pecahan. Sehingga algoritma ini diklaim lebih baik dalam hal pemrosesan titik koordinat.

 Berikut ini adalah langkah-langkah penerapan Bresenham Line Algorithm;

1.     Tentukan koordinat awal garis dan koordinat akhir. A(x1, y1) dan B(x2, y2)

2.     Hitung nilai dx, dari perhitungan (x2 – x1), kemudian nilai dy dari perhitungan (y2 – y1)

3.     kemudian hitung nilai Parameter, P0 = 2dy – dx

4.     pastikan iterasi setiap titik pada garis tersebut berawal dari k = 0.

5.     Cek ketentuan untuk proses iterasi yang digunakan

1)     Jika Pk < 0 , maka

·       titik koordinat selanjutnya adalah (xk + 1, yk )

·       dan Pk+1 = Pk + 2dy

2)     Jika sebaliknya, maka

·       koordinat selanjutnya adalah (xk + 1, yk + 1)

·       dan Pk+1 = Pk + 2dy – 2dx

6.     Ulangi kembali proses pada step ke-5 diatas pada setiap iterasi titik berikutnya, sampai bertemu dengan titik koordinat akhir dari garis.

ALGORITMA MID POINT (Lingkaran Ttik Tengah)

Algoritma midpoint juga disebut algoritma lingkaran Bressenham. Pembentukan semua titik berdasarkan titik pusat dengan penambahan semua jalur di sekeliling lingkaran. Komputasi untuk membuat kurva lingkaran dimulai dengan mengidentifikasi bagian-bagian dari lingkaran yang dapat ditentukan dengan menggunakan sifat simetri, hal ini dilakukan dengan cara membagai lingkaran dengan masing-masing mempunyai sudut sebesar 45° , sehingga dalam sebuah lingkaran dibagi menjadi 8 bagian.

Langkah- langkah untuk membentuk lingkaran algoritma circle midpoint:

1.     Tentukan radius r dengan titk pusat lingkaran(xc,yc) kemudian diperoleh (x0,y0) = (0,r)

2.     Hitung nilai dari parameter P₀ = 5/4 – r

3.     Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut: Bila Pk < 0, maka titik selanjutnya adalah (x_k+1 ,y_k ) dan Parameter selanjutnya P_k+1 =P_k + 2x_k+1 + 1 Bila tidak Pk > 0, maka selanjutnya adalah (x_k+1 ,y_k-1 )dan Parameter selanjutnya P_k+1=P_k + 2x_k+1 + 1 – 2y_k+1 Dimana 2x_k+1 = 2x_k + 2 dan 2y_k+1 = 2y_k – 2

4.     Tentukan titik simetris pada ketujuh oktan yang lain

5.     Gerakkan setiap posisi pixel(x,y) pada garis melingkar dari lingkaran dengan titik pusat (xc,yc) dan tentukan nilai koordinat: X_k+1 = x_k + 1 dan Y_k+1 = yk , atau Y_k+1 = yk -1

6.     Ulangi langkah ke3 sampai 5, sehingga X >= y

Referensi :

https://www.anakblogger.com/2020/04/pengertian-algoritma-dda-digital.html

https://belangtelon.blogspot.com/2010/12/algoritma-digital-differential-analyzer.html

https://robyyuliardi.wordpress.com/2014/10/08/algoritma-dda-digital-differential-analyzer/

https://tambunan.staff.telkomuniversity.ac.id/mainan-2-grafcit-algoritma-dda-vs-bressenham/

https://pradsource.blogspot.com/2018/04/line-algorithm.html

https://ilairnawati11.wordpress.com/2018/10/23/algoritma-pembentuk-lingkaran/