सर्कल जनरेशन एल्गोरिथम

स्क्रीन पर एक वृत्त खींचना एक रेखा खींचने की तुलना में थोड़ा जटिल है। एक सर्कल बनाने के लिए दो लोकप्रिय एल्गोरिदम हैं -Bresenham’s Algorithm तथा Midpoint Circle Algorithm। ये एल्गोरिदम सर्कल को खींचने के लिए आवश्यक बाद के बिंदुओं को निर्धारित करने के विचार पर आधारित हैं। आइए हम एल्गोरिदम पर विस्तार से चर्चा करें -

वृत्त का समीकरण $ X ^ {2} + Y ^ {2} = r ^ {2}, $ है जहाँ r त्रिज्या है।

ब्रेसेनहम का एल्गोरिथम

हम रेखापुंज प्रदर्शन पर एक निरंतर चाप प्रदर्शित नहीं कर सकते। इसके बजाय, हमें चाप को पूरा करने के लिए निकटतम पिक्सेल स्थिति चुननी होगी।

निम्नलिखित उदाहरण से, आप देख सकते हैं कि हमने पिक्सेल को (X, Y) स्थान पर रखा है और अब यह तय करने की आवश्यकता है कि अगला पिक्सेल कहाँ रखा जाए - N (X + 1, Y) या S (X + 1) पर Y-1)।

यह निर्णय पैरामीटर द्वारा तय किया जा सकता है d

  • यदि d <= 0, तो N (X + 1, Y) को अगले पिक्सेल के रूप में चुना जाना है।
  • यदि d> 0, तो S (X + 1, Y-1) को अगले पिक्सेल के रूप में चुना जाना है।

कलन विधि

Step 1- सर्कल और त्रिज्या के केंद्र के निर्देशांक प्राप्त करें, और उन्हें क्रमशः x, y और R में संग्रहीत करें। सेट पी = 0 और क्यू = आर।

Step 2 - निर्णय पैरामीटर D = 3 - 2R सेट करें।

Step 3 - चरण -8 के माध्यम से दोहराएं जबकि पी। क्यू।

Step 4 - कॉल ड्रा सर्कल (एक्स, वाई, पी, क्यू)।

Step 5 - P का मान बढ़ाएँ।

Step 6 - यदि D <0 तो D = D + 4P + 6।

Step 7 - एसेट सेट R = R - 1, D = D + 4 (PQ) + 10।

Step 8 - कॉल ड्रा सर्कल (एक्स, वाई, पी, क्यू)।

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

मध्य बिंदु एल्गोरिथम

Step 1 - इनपुट त्रिज्या r और सर्कल केंद्र $ (x_ {c,} y_ {c}) $ और मूल पर केंद्रित सर्कल की परिधि पर पहला बिंदु प्राप्त करें

(x0, y0) = (0, r)

Step 2 - के रूप में निर्णय पैरामीटर के प्रारंभिक मूल्य की गणना करें

$ P_ {0} $ = 5/4 - r (इस समीकरण के सरलीकरण के लिए निम्नलिखित विवरण देखें।)

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 - प्रत्येक $ X_ {K} $ स्थिति K = 0 पर शुरू होती है, निम्नलिखित परीक्षण करें -

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 - अन्य सात अष्टक में समरूपता बिंदु निर्धारित करें।

Step 5 - $ (X_ {C,} Y_ {C}) $ पर केंद्रित वृत्ताकार पथ पर प्रत्येक परिकलित पिक्सेल स्थिति (X, Y) को स्थानांतरित करें और समन्वय मूल्यों को प्लॉट करें।

X = X + XC,   Y = Y + YC

Step 6 - चरण 3 को 5 तक दोहराएँ जब तक X> = Y।