Setelah sebelumnya membahasa algoritma DDA dan Bresenham, sekarang aku mau
share tentang algoritma
midpoint circle untuk lingkaran dan ellips.
Persamaan Lingkaran
• Lingkaran dapat digambarkan dengan menggunakan
persamaan koordinat rectangular tsb akan tetapi
pendekatan ini menimbulkan dua masalah yaitu :
– Persamaan tersebut mengandung perhitungan akar yang
operasinya memakan waktu.
– Timbul gap yang cukup signifikan pada lingkaran ketika
digambarkan.
Midpoint Circle Algorithm
• Untuk mengatasi masalah yang timbul dari penerapan koordinat polar maupun rectangular, Bresenham menyusun suatu algoritma pembentukan lingkaran yang hanya menggunakan aritmetika integer. Secara prinsip algoritma ini sejenis dengan algoritma penggambaran garis yang disusun oleh orang yang sama.
• Lingkaran merupakan objek yang simetris sehingga karakteristik ini dapat dimanfaatkan untuk mengurangi pekerjaan pada saat menggambar lingkaran. Lingkaran dibagi menjadi 8 oktan (lihat
gambar 3.x), misalkan kita menyusun algoritma untuk menggambarkan lingkaran di oktan pertama, maka koordinat untuk 7 oktan selanjutnya dapat ditentukan.
Midpoint Circle Algorithm
Langkah-langkah mengerjakan algortima midpoint circle
1. Input jari-jari (r) dan koordinar pusat lingkaran (xc,yc), kemudian tentukan koordinat untuk titik awal (xo,yo) = (x, r)
2. Hitung nilai awal untuk parameter keputusan Po = 1 - r
3. Untuk setiap xk, mulai dari k = 0, periksa/cek kondisi berikut :
- Jika nilai pk < 0 maka, titik selanjutnya pada lingkaran dgn pusat (0,0) adalah xk+1=x +1, nilai y tetap; dan pk+1 = pk + 2.x + 1
Selain itu berarti,
- pk > 0 maka, titik selanjutnya adalah xk+1 = x + 1, yk+1 = y - 1; dan pk+1 = pk + 2x - 2y + 1
4. Ulangi langkah 3 sampai 4, hentikan perhitungan ketika x > atau = y
Contoh 1 :
x^2 + y^2 = 100
Dari mana y = 10 ? liat tabel pada plot awal (x,y)=(x,r) = (0,10)
ternyata 100 apabila di akar kan, maka hasilnya sama dengan 10
Po = 1 - r = 1 - 10 = -9
jadi, skrng jari-jarinya sudah diketahui = 10 dan 2x = 0, 2y = 20 , pk = -9
Nah.. tinggal menghitung k, dimulai dari k=0, sampai batas yang di tentukan (x > atau = y).
Liat Algoritma midpoint circle dan Perhatikan Langkah-langkah mengerjakan algortima midpoint circle!
k=0
pk = 1 - r = 1 - 10 = -9
periksa pk, pk < 0 maka,
xk+1 = 0 + 1 =
1 , nilai
10 tetap;
pk+1 = pk + 2.x + 1
= -9 + 2 .1 + 1 = -6
2x = 2
2y = 20
k=1
periksa pk, pk < 0 maka,
xk+1 = 1 + 1 =
2 , nilai
10 tetap;
pk+1 = pk + 2.x + 1
= -6 + 2 . 2 + 1 = -1
2x = 4
2y = 20
k=2
periksa pk, pk < 0 maka,
xk+1 = 2 + 1 =
3 , nilai
10 tetap;
pk+1 = pk + 2.x + 1
= -1 + 2 . 3 + 1 = 6
2x = 6
2y = 20
k=3
periksa pk, pk > 0 maka,
xk+1 = 3 + 1 =
4, yk+1 = 10 - 1 =
9
pk+1 = pk + 2x - 2y + 1
= 6 + 2 . 4 - 2 . 9 + 1 = 6 + 8 - 18 + 1 = -3
2x = 8
2y = 18
Lanjutkan sampai (x > atau = y), selesai.
Contoh 2 :
1.Diketahui titik pusat lingkaran (0,0) dan radius 8, perhitungan berdasarkan otktan dari kuadran
pertama dimana x = 0 hingga y = 0. Nilai parameter dapat ditentukan dengan Po = 1 - r (jari-jari).
Buatlah garis lingkaran dengan algoritma midpoint circle?
Penyelesaian :
koordinat titik pusat sama dengan kuadran pertama (x,y) = (x, r) = (0,8)
Po = 1 - r
= 1 - 8 = -7
K
|
PK
|
( xk + 1, yk + 1)
|
-
|
-
|
0,8
|
0
|
-7
|
1,8
|
1
|
-4
|
2,8
|
2
|
1
|
3,8
|
3
|
-6
|
4,7
|
4
|
3
|
5,7
|
5
|
0
|
6,6
|
k=0
pk= 1 - r = 1 - 8 = -7
periksa pk, pk < 0 maka,
xk = x + 1 = 0 + 1 =
1 , nilai y tetap
8 ;
k=1
periksa pk, pk < 0 maka,
xk = x + 1 = 1 + 1 =
2 , nilai y tetap
8 ;
pk+1 = pk + 2.x + 1
= -7 + 2 . 1 + 1 = -4
k=2
periksa pk, pk < 0 maka,
xk = x + 1 = 2 + 1 =
3 , nilai y tetap
8;
pk+1 = pk + 2.x + 1
= - 4 + 2 . 2 + 1 = 1
k=3
periksa pk, pk > 0 maka,
xk = x + 1 = 3 + 1 =
4 ; yk = y - 1 = 8 - 1 =
7
pk+1 = pk + 2x - 2y + 1
= 1 + 2.
3 - 2.
7 + 1 = 1 + 6 - 14 + 1= -6
k=4
periksa pk, pk < 0 maka,
xk = x + 1 = 4 + 1 =
5 , nilai y tetap
7;
pk+1 = pk + 2.x + 1
= - 6 + 2 . 4 + 1 = 3
k=5
periksa pk, pk > 0 maka,
xk = x + 1 = 5 + 1 =
6 ; yk = y - 1 = 7 - 1 =
6
pk+1 = pk + 2x - 2y + 1
= 1 + 2.
5 - 2.
6 + 1 = 1 + 10 - 12 + 1= 0
Proses di hentikan karena (x > atau = y).
Kode Program Lingkaran akan di suguhkan nanti.. Stay tuned!!
Latihan
Dengan menggunakan midpoint circle algortihm, buat
lingkaran berdasarkan persamaan berikut ini :
– x 2 + y 2 = 64
– x 2 + y 2 = 49
