ALGORITMA DDA, BRESENHAM DAN MIDPOINT CIRCLE

Nama : Habib Maulana

Kelas : 3IA18

NPM : 50420527

 Pengertian Algoritma DDA

Algoritma adalah metode efektif diekspresikan sebagai rangkaian terbatas dari instruksi-instruksi yang telah didefinisikan dengan baik untuk menghitung sebuah fungsi.

Algoritma DDA adalah algoritma pembentukan garis berdasarkan perhitungan dx maupun dy, menggunakan rumus dy=m.dx. Semua koordinat titik yang membentuk garis diperoleh dari perhitungan kemudian dikonversikan menjadi nilai integer.

Contoh Soal:

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.

Δx = x1 — x 0 = 17–10 = 7

Δy = y1 — y0 = 16 -10 = 6

selanjutnya hitung dan bandingkan nilai absolutnya.

|Δx| = 7

|Δy| = 6

karena |Δx| > |Δy|, maka step = |Δx| = 7, maka diperoleh :

x_inc = 7/7= 1

y_inc = 6/7 = 0,86 .

Algoritma Bresenham

Algoritma Garis Bresenham adalah suatu algoritma yang menentukan titik-titik dalam dimensi yang membentuk pendekatan dekat dengan garis lurus antara dua titik yang diberikan. Pendekatan ini biasa digunakan untuk menggambar garis pada layar komputer, karena hanya menggunakan integer penambahan, pengurangan dan pergeseran. Algoritma ini merupakan salah satu algoritma paling awal yang dikembangkan di bidang komputer grafis.

Contoh soal:

Hitung posisi pixel hingga membentuk sebuah garis yang menghubungkan titik (10 , 4) dan (16 ,8) !

Jawab :

(x_0,y_{0) = (}10,4)

∆x =16-10=6  ,  ∆y=8-4=4  ,  2∆y=8  ,  2∆y-2∆x=8-12= -4

p₀=2∆y-∆x=8-6=2

 

Cara mencarinya:

• k=0

p_k=p₀=2

2 > 0 maka x_k+1,y_k+1 = 10+1,4+1= 11,5

• k=1

p_k=p₀₊₁=p_k+2∆y-2∆x

p₁₌ 2+(-4)=-2

-2 < 0 maka x_k+1,y_k = 11+1,5 = 12,5

• k=2

p_k=p₁₊₁=p_k+2∆y

p₂=-2+8=6

6 > 0 maka x_k+1,y_k+1 = 12+1,5+1 = 13,6

• k=3

p_k=p₂₊₁=p_k+2∆y-2∆x

p₃=6+(-4)=2

2 > 0 maka x_k+1,y_k+1 = 13+1,6+1 = 14,7

• k=4

p_k=p₃₊₁=p_k+2∆y-2∆x

p₄=2+(-4)=-2

-2 < 0 maka x_k+1,y_k = 14+1,7 =15,7

• k=5

p_k=p₄₊₁=p_k+2∆y

p₅=-2+8=6

6 > 0 maka x_k+1,y_k+1 = 15+1,7+1 = 16,8

 

k	pk	xk+1,yk+1
0	2	11 , 5
1	-2	12 , 5
2	6	13 , 6
3	2	14 , 7
4	-2	15 , 7
5	6	16 , 8

Algoritma 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 PUSTAKA

  https://medium.com/@dirat17/pengertian-algoritma-dda-dan-contoh-soal-53622c28b1e3

http://yunus-fanani.blogspot.com/2013/05/algoritma-dda-bresenham.html

https://yudhi06.wordpress.com/2009/03/12/algoritma-mid-point-lingkaran-ttik-tengah/

https://she2008.wordpress.com/2011/01/13/algoritma-bresenham/