DDA (Digital Differential Analyzer)
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 :
Tentukan dua titik yang akan dihubungkan.
Tentukan salah satu titik sebagai titik awal (x0, y0) dan titik akhir (x1, y1).
Hitung Δx = x1 – x0 dan Δ y = y1 – y0.
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|.
Hitung penambahan koordinat pixel yaitu x_increment = Δx / step dan y_increment = Δy / step.
Koordinat selanjutnya (x+x_incerement, y+y_increment).
Posisi pixel pada layer ditentukan dengan pembulatan nilai koordinasi tersebut.
Ulangi step 6 dan 7 untuk menentukan posisi pixel selanjutnya, sampai x = x1 dan y = y1
BRESENAM
Algoritma bresenham merupakan suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). Bagian pengkonversian (scan-knversi) garis akan melakukan kalkulasi untuk penambahan nilai-nilai integer (yang dibutuhkan untuk membentuk garis) yang disesuaikan dengan tipe grafik yang dipakai oleh layar komputer (keadaan monitor pc) kita. Untuk mengilustrasikan pendekatan bresenham, pertama kita harus memperhatikan proses scan- konvensi untuk garis dengan slope positif yang lebih kecil dari 1. Posisi pixel sepanjang line-path kemudian ditentukan dengan penyamplingan pada unit interval x.dimulai dari endpoint kiri (Xo,Yo) dari garis yang diberikan, kita pindahkan beberapa kolom berturut-turut (berdasarkan posisi x) dan plot pixel-pixel yang mempunyai nilai scan-line y ke jarak yang paling dekat dengan line-path.
Langkah umum algoritma Bresenham
1. Tentukan titik awal dan akhir
- Titik awal (X1,Y1)
- Titik akhir (X2, Y2)
2. Tentukan Nilai pengubahan posisi (P)
- DX = X2 - X1
- DY = Y2 - Y1
- P (Awal) = 2 * DY - DX
Jika P < 0 maka X = X + 1, Nilai Y Tetap
(P) Selanjutnya adalah P = P + (2 * DY)
Jika tidak maka X = X + 1, Y = Y + 1
(P) Selanjutnya adalah P = P + 2 * (DY - DX)
3. Perulangan
rumus yang di pakai dalam perulangan tergantung kondisi (P) apakah P > 0, P< 0.
setelah itu gunakan rumus sesuai kondisi (P)
MIDPOINT CIRCLE
Algoritma Lingkaran Midpoint juga disebut algoritma lingkaran Bressenham. Bressenham mengembangkan generator lingkaran yang cukup efisien. 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, yaitu oktan kedua dari x=0 ke x=R/Ö2, dan menggunakan CirclePoints untuk menampilkan titik dari seluruh lingkaran.
Langkah langkah untuk membentuk lingkaran algoritma Circle Midpoint:
Tentukan radius r dengan titk pusat lingkaran(xc,yc) kemudian diperoleh(x0,y0)=(0,r)
Hitung nilai dari parameter P0=5/4r
Tentukan nilai awal k=0, untuk setiap posisi xk berlaku sebagai berikut:
oBila Pk< 0, maka titik selanjutnya adalah (xk+1,yk))dan Pk+1=Pk+2xk+1+1
Bila tidak, maka selanjutnya adalah(xk+yk-1), dan Pk+Pk+2xk+12yk+1 Dimana 2xk+1=2xk+2 dan 2yk+=2yk2
-
Tentukan titik simetris pada ketujuh oktan yang lain
-
Gerakkan setiap posisi pixel(x,y) pada garis melingkar dari lingkaran dengan titik pusat (xc,yc) dan tentukan nilai koordinat: x=x+xcy=y+yc
Ulangi langkah ke3 sampai 5, sehingga x>=y
Daftar Pusaka
- https://robyyuliardi.wordpress.com/2014/10/08/algoritma-dda-digital-differential-analyzer/
- https://suryosantoso14.blogspot.com/2016/11/algoritma-dda-bresenham-dan-algoritma.html
- https://yudhi06.wordpress.com/2009/03/12/algoritma-mid-point-lingkaran-ttik-tengah/
