Algoritma Generasi Lingkaran
Menggambar lingkaran di layar agak rumit daripada menggambar garis. Ada dua algoritma populer untuk menghasilkan lingkaran -Bresenham’s Algorithm dan Midpoint Circle Algorithm. Algoritma ini didasarkan pada gagasan untuk menentukan titik-titik selanjutnya yang diperlukan untuk menggambar lingkaran. Mari kita bahas algoritma secara rinci -
Persamaan lingkarannya adalah $ X ^ {2} + Y ^ {2} = r ^ {2}, $ dengan r adalah jari-jari.
Algoritma Bresenham
Kami tidak dapat menampilkan busur berkelanjutan pada tampilan raster. Sebagai gantinya, kita harus memilih posisi piksel terdekat untuk menyelesaikan busur.
Dari ilustrasi berikut, Anda dapat melihat bahwa kita telah meletakkan piksel di lokasi (X, Y) dan sekarang perlu memutuskan di mana meletakkan piksel berikutnya - di N (X + 1, Y) atau di S (X + 1, Y-1).
Ini dapat ditentukan oleh parameter keputusan d.
- Jika d <= 0, maka N (X + 1, Y) akan dipilih sebagai piksel berikutnya.
- Jika d> 0, maka S (X + 1, Y-1) akan dipilih sebagai piksel berikutnya.
Algoritma
Step 1- Dapatkan koordinat dari pusat lingkaran dan jari-jari, dan simpan masing-masing dalam x, y, dan R. Atur P = 0 dan Q = R.
Step 2 - Tetapkan parameter keputusan D = 3 - 2R.
Step 3 - Ulangi melalui langkah-8 saat P ≤ Q.
Step 4 - Panggil Draw Circle (X, Y, P, Q).
Step 5 - Tingkatkan nilai P.
Step 6 - Jika D <0 maka D = D + 4P + 6.
Step 7 - Set Lain R = R - 1, D = D + 4 (PQ) + 10.
Step 8 - Panggil Draw Circle (X, Y, P, Q).
Draw Circle Method(X, Y, P, Q).
Call Putpixel (X + P, Y + Q).
Call Putpixel (X - P, Y + Q).
Call Putpixel (X + P, Y - Q).
Call Putpixel (X - P, Y - Q).
Call Putpixel (X + Q, Y + P).
Call Putpixel (X - Q, Y + P).
Call Putpixel (X + Q, Y - P).
Call Putpixel (X - Q, Y - P).
Algoritma Titik Tengah
Step 1 - Radius masukan r dan pusatkan lingkaran $ (x_ {c,} y_ {c}) $ dan dapatkan titik pertama pada keliling lingkaran yang berpusat pada titik asal sebagai
(x0, y0) = (0, r)
Step 2 - Hitung nilai awal parameter keputusan sebagai
$ P_ {0} $ = 5/4 - r (Lihat penjelasan berikut untuk penyederhanaan persamaan ini.)
f(x, y) = x2 + y2 - r2 = 0
f(xi - 1/2 + e, yi + 1)
= (xi - 1/2 + e)2 + (yi + 1)2 - r2
= (xi- 1/2)2 + (yi + 1)2 - r2 + 2(xi - 1/2)e + e2
= f(xi - 1/2, yi + 1) + 2(xi - 1/2)e + e2 = 0
Let di = f(xi - 1/2, yi + 1) = -2(xi - 1/2)e - e2
Thus,
If e < 0 then di > 0 so choose point S = (xi - 1, yi + 1).
di+1 = f(xi - 1 - 1/2, yi + 1 + 1) = ((xi - 1/2) - 1)2 + ((yi + 1) + 1)2 - r2
= di - 2(xi - 1) + 2(yi + 1) + 1
= di + 2(yi + 1 - xi + 1) + 1
If e >= 0 then di <= 0 so choose point T = (xi, yi + 1)
di+1 = f(xi - 1/2, yi + 1 + 1)
= di + 2yi+1 + 1
The initial value of di is
d0 = f(r - 1/2, 0 + 1) = (r - 1/2)2 + 12 - r2
= 5/4 - r {1-r can be used if r is an integer}
When point S = (xi - 1, yi + 1) is chosen then
di+1 = di + -2xi+1 + 2yi+1 + 1
When point T = (xi, yi + 1) is chosen then
di+1 = di + 2yi+1 + 1
Step 3 - Pada setiap posisi $ X_ {K} $ mulai dari K = 0, lakukan tes berikut -
If PK < 0 then next point on circle (0,0) is (XK+1,YK) and
PK+1 = PK + 2XK+1 + 1
Else
PK+1 = PK + 2XK+1 + 1 – 2YK+1
Where, 2XK+1 = 2XK+2 and 2YK+1 = 2YK-2.
Step 4 - Tentukan titik simetri di tujuh oktan lainnya.
Step 5 - Pindahkan setiap menghitung posisi piksel (X, Y) ke jalur melingkar yang berpusat di $ (X_ {C,} Y_ {C}) $ dan plot nilai koordinat.
X = X + XC, Y = Y + YC
Step 6 - Ulangi langkah-3 sampai 5 sampai X> = Y.