Thuật toán tạo vòng tròn

Vẽ một vòng tròn trên màn hình hơi phức tạp hơn vẽ một đường thẳng. Có hai thuật toán phổ biến để tạo vòng kết nối -Bresenham’s Algorithm và Midpoint Circle Algorithm. Các thuật toán này dựa trên ý tưởng xác định các điểm tiếp theo cần thiết để vẽ vòng tròn. Hãy để chúng tôi thảo luận chi tiết về các thuật toán -

Phương trình của đường tròn là $ X ^ {2} + Y ^ {2} = r ^ {2}, $ với r là bán kính.

Thuật toán Bresenham

Chúng tôi không thể hiển thị một cung liên tục trên màn hình raster. Thay vào đó, chúng ta phải chọn vị trí pixel gần nhất để hoàn thành vòng cung.

Từ hình minh họa sau, bạn có thể thấy rằng chúng tôi đã đặt pixel tại vị trí (X, Y) và bây giờ cần quyết định vị trí đặt pixel tiếp theo - tại N (X + 1, Y) hoặc tại S (X + 1, Y-1).

Điều này có thể được quyết định bởi tham số quyết định d.

• Nếu d <= 0, thì N (X + 1, Y) sẽ được chọn làm pixel tiếp theo.
• Nếu d> 0, thì S (X + 1, Y-1) sẽ được chọn làm pixel tiếp theo.

Thuật toán

Step 1- Lấy tọa độ tâm của hình tròn và bán kính, lưu chúng vào x, y và R tương ứng. Đặt P = 0 và Q = R.

Step 2 - Đặt tham số quyết định D = 3 - 2R.

Step 3 - Lặp lại bước 8 trong khi P ≤ Q.

Step 4 - Gọi Draw Circle (X, Y, P, Q).

Step 5 - Tăng giá trị của P.

Step 6 - Nếu D <0 thì D = D + 4P + 6.

Step 7 - Đặt khác R = R - 1, D = D + 4 (PQ) + 10.

Step 8 - Gọi 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).

Thuật toán điểm giữa

Step 1 - Bán kính đầu vào r và đường tròn tâm $ (x_ {c,} y_ {c}) $ và lấy điểm đầu tiên trên chu vi của đường tròn có tâm ở điểm gốc là

(x0, y0) = (0, r)

Step 2 - Tính giá trị ban đầu của tham số quyết định như

$ P_ {0} $ = 5/4 - r (Xem mô tả sau để đơn giản hóa phương trình này.)

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 - Tại mỗi vị trí $ X_ {K} $ bắt đầu từ K = 0, thực hiện kiểm tra sau:

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 - Xác định các điểm đối xứng trong bảy bát phân khác.

Step 5 - Di chuyển từng vị trí pixel tính toán (X, Y) vào đường tròn có tâm là $ (X_ {C,} Y_ {C}) $ và vẽ các giá trị tọa độ.

X = X + XC,   Y = Y + YC

Step 6 - Lặp lại bước 3 đến bước 5 cho đến khi X> = Y.