ALGORITMA DIGITAL DIFFERENTIAL ANALYZER, BRESENHAM, DAN MIDPOINT CIRCLE

A. Algoritma Digital Differential Analyzer (DDA)

Pengertian

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.

Langkah-langkah

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.

Contoh

Diketahui 2 buah titik A(2,1) dan titik B(8,5). Bila titik A sebagai titik awal dan titik B sebagai titik akhir, maka buatlah garis yang menghubungkan titik tersebut dengan menggunakan algoritma DDA.

Jawaban :

Titik awal (x1, y1) = A(2,1) dan Titik akhir (x2, y2) = B(8,5)
dx = x2 − x1 = 8 −2 = 6   dan  dy = y2 − y1 = 5 − 1 = 4
Karena: |dx| >  |dy|, maka step = |dx| = 6
x_inc = dx / step =  6/6 = 1 y_inc = dy / step =  4/6 = 0,67

*Iterasi ke-1: (x,y) = (2,1)
x+x_inc = 2 + 1 = 3
y+y_inc = 1 + 0,67 = 1,67
Koordinat selanjutnya : (x,y) = (3; 1,67)
Pembulatan (3; 1,67) ≈ (3,2). Gambar titik (3,2) dilayar.

*Iterasi ke-2: (x,y) = (3;  1,67)
x+x_inc = 3 + 1 = 4
y+y_inc = 1,67 + 0,67 = 2,34
Koordinat selanjutnya : (x,y) = (4;  2,34)
Pembulatan (4;  2,34) ≈ (4,2). Gambar titik (4,2) dilayar.

*Iterasi ke-3: (x,y) = (4;  2,34)
xA+x_inc = 4 + 1 = 5
yA+y_inc = 2,34 + 0,67= 3,01
Koordinat selanjutnya : (x,y) = (5;   3,01)
Pembulatan (5;   3,01) ≈ (5,3). Gambar titik (5,3) dilayar.

*Iterasi ke-4: (x,y) = (5;  3,01)
xA+x_inc = 5 + 1 = 6
yA+y_inc = 3,01 + 0,67 = 3,68
Koordinat selanjutnya : (x,y) = (6;   3,68)
Pembulatan (6;   3,68) ≈ (6,4). Gambar titik (6,4) dilayar.

*Iterasi ke-5: (x,y) = (6;  3,68)
xA+x_inc = 6 + 1 = 7
yA+y_inc = 3,68 + 0,67 = 4,35
Koordinat selanjutnya : (x,y) = (7;   4,35)
Pembulatan (7;   4,35) ≈ (7,4). Gambar titik (7,4) dilayar.

*Iterasi ke-6: (x,y) = (7;  4,35)
xA+x_inc = 7 + 1 = 8
yA+y_inc = 4,35 + 0,67 = 5,02
Koordinat selanjutnya : (x,y) = (8;   5,02)
Pembulatan (8;   5,02) ≈ (8,5). Gambar titik (8,5) dilayar.

Karena x = x2 = 8, maka iterasi dihentikan. Sehingga, diperoleh titik-titik pembentuk garis sebagai berikut: (2,1), (3,2), (4,2), (5,3), (6,4), (7,4), dan (8,5).

B. Algoritma Bresenham

Pengertian

Algoritma bresenham merupakan suatu algoritma (pendekatan) yang dikreasikan oleh bresenham yang tidak kalah akurat dan efisien dengan algoritma primitif lainnya (seperti DDA). 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.

Langkah-langkah

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.

Proses iterasi akan berhenti pada posisi titik akhir garis, dan tidak ada proses pembulatan hasil.

Contoh

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

p_k=p₀=2

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

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

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

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

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

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	p_k	x_k+1,y_k+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

C. Algoritma Midpoint Cicrle

Pengertian

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.

Langkah-langkah

Berikut adalah langkah-langkah penerapan Algoritma Midpoint Circle :

1. Tentukan radius r dengan titk pusat lingkaran(xcenter,ycenter) kemudian diperoleh titik awal (x,r).

2. Hitung nilai parameter P0=1-r.

3. 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

4. Tentukan titik simetris pada ketujuh oktan yang lain.

5. Ulangi langkah 3 dan 4, sampai nilai x>=y.

Contoh

Diketahui titik pusat lingkaran (0,0) dan radius 8, perhitungan berdasarkan oktan dari kuadran pertama dimana x = 0 sampai y = 0. Nilai parameter dapat ditentukan dengan P0 = 1 – r = 1 – 8 = -7
Koordinat titik awal adalah (x,r) = (0,8)

Jawab:

X = 0 Y = r = 8

K=0
P = 1 – r
= 1 – 8 = -7

Loop ke-1
x = x +1 y tetap è 8
= 0 +1 = 1

K=1
P = P + 2 * X + 1
= -7 + 2 * 1 + 1
= -4
Loop ke-2
x = x +1 y tetap è 8
= 1 +1 = 2

K=2
P = P + 2 * X + 1
= -4 + 2 * 2 + 1
= 1
Loop ke-3
x = x +1 y = y-1
= 2 +1 = 3 = 8-1 = 7

K=3
P = P + 2 * (X –Y) +1
= 1 + 2 * (3 – 7) + 1
= -6
Loop ke-4
x = x +1 y tetap è 7
= 3 +1 = 4

K=4
P = P + 2 * X + 1
= -6 + 2 * 4 + 1
= 3
Loop ke-5
x = x +1 y = y-1
= 4 +1 = 5 = 7-1 = 6

K=5
P = P + 2 * (X – Y) + 1
= 3 + 2 *(5 – 6) + 1
= 2
Loop ke-6
x = x +1 y = y-1
= 5 +1 = 6 = 6-2 = 5

K=6
P = P + 2 * (X – Y) + 1
= 2 + 2 *(6 – 5) + 1
= 5 Loop berhenti karena x > y

K	Pk	(X_k+1 , Y_k+1) Oktan 1
–	–	(0,8)
0	-7	(1,8)
1	-4	(2,8)
2	1	(3,7)
3	-6	(4,7)
4	3	(5,6)
5	2	(6,5)

Referensi :

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

https://prnm17.blogspot.com/2019/11/pengertian-algoritma-dda-beserta-soal.html

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

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

https://mikebco.wordpress.com/2012/05/18/algoritma-midpoint-circle/

https://fitria08stmik.wordpress.com/2011/04/03/tugas-grafika-komputer-conoth-soal-algoritma/

Cari Blog Ini

All rounded blog