Mid-Point Circle Algorithm

Circle Generation Algorithms & Mathematical Equations (বৃত্ত অঙ্কন অ্যালগরিদম ও গাণিতিক সমীকরণ)

কম্পিউটার গ্রাফিক্স এবং স্ক্যান-কনভার্সনে সোজা লাইন আঁকার চেয়ে বৃত্ত বা বাঁকা শেপ (Curved Shapes) তৈরি করা বেশ জটিল। সোজা লাইনের ক্ষেত্রে সম্পূর্ণ রেখা জুড়ে ঢাল $m$ ধ্রুবক থাকে, কিন্তু বৃত্তের ক্ষেত্রে পরিধি জুড়ে ঢাল ক্রমাগত $0$ থেকে $\infty$ (অসীম) পর্যন্ত পরিবর্তন হতে থাকে।

পিক্সেল গ্রিডে সঠিকভাবে বৃত্ত প্লট করার জন্য প্রথমেই বৃত্তের গাণিতিক রূপ—কার্তেসীয় (Cartesian) এবং পোলার (Polar) সমীকরণ বিশ্লেষণ করা প্রয়োজন।

১. কার্তেসীয় রূপ (Cartesian Form)

মূলবিন্দু $(0, 0)$-এ কেন্দ্র এবং $R$ ব্যাসার্ধবিশিষ্ট বৃত্তের স্ট্যান্ডার্ড কার্তেসীয় সমীকরণ হলো:

$x^2 + y^2 = R^2$

যদি বৃত্তের কেন্দ্র যেকোনো স্থানাঙ্ক $(x_c, y_c)$-এ অবস্থিত হয়, তবে সমীকরণটি হবে:

$(x - x_c)^2 + (y - y_c)^2 = R^2$

$x$-এর সাপেক্ষে $y$-এর মান বের করলে পাই:

$y = \pm \sqrt{R^2 - (x - x_c)^2} + y_c$

২. পোলার রূপ (Polar Form)

ত্রিকোণমিতিক প্যারামেট্রিক সমীকরণ ব্যবহার করে $(x_c, y_c)$ কেন্দ্রে অবস্থিত বৃত্তের পরিধির যেকোনো বিন্দু $(x, y)$-কে কোণ $\theta$-এর মাধ্যমে প্রকাশ করা যায়:

$x = x_c + R \cdot \cos\theta$

$y = y_c + R \cdot \sin\theta$

এখানে কোণ $\theta$-এর মান $0^\circ$ থেকে $360^\circ$ ($0$ থেকে $2\pi$ রেডিয়ান) পর্যন্ত পরিবর্তিত হয়।

---

Problems with Direct Circle Drawing Methods (সরাসরি বৃত্ত আঁকার সমস্যাসমূহ)

গাণিতিকভাবে কার্তেসীয় এবং পোলার সমীকরণ সঠিক হলেও কম্পিউটার অ্যালগরিদমে সরাসরি এগুলো ব্যবহার করে বৃত্ত আঁকতে গেলে মারাত্মক পারফরম্যান্স ও গ্রাফিক্যাল সমস্যা দেখা দেয়।

---

8-Fold Symmetry / Octant Symmetry (৮-গুণ প্রতিসাম্য)

বৃত্তের এই গাণিতিক সীমাবদ্ধতা দূর করতে আমরা বৃত্তের জ্যামিতিক ৮-গুণ প্রতিসাম্য (8-Fold Symmetry) সুবিধা ব্যবহার করি।

মাত্র ১ম ৪৫° সেক্টর (অকট্যান্ট ২) গণনা

পুরো ৩৬০° ঘুরার বদলে আমরা কেবল দ্বিতীয় অকট্যান্টে (Octant 2) অবস্থিত ৪৫° চাপের পিক্সেল স্থানাঙ্ক হিসাব করি—যা $x = 0, y = R$ বিন্দু থেকে শুরু হয়ে $x = y = \frac{R}{\sqrt{2}}$ পর্যন্ত বিস্তৃত।

এই একটি প্রাইমারি অকট্যান্টে নির্ণীত প্রতিটি পিক্সেল $(x, y)$-এর জন্য প্রতিসাম্য ব্যবহার করে একই সাথে বাকি ৭টি অকট্যান্টের পিক্সেল প্লট করা হয়:

---

Mid-Point Circle Algorithm & Incremental Decision Variable (মিডপয়েন্ট অ্যালগরিদম)

Mid-Point Circle Algorithm (যাকে ব্রেসেনহ্যামের সার্কেল অ্যালগরিদমও বলা হয়) ত্রিকোণমিতি, বর্গমূল এবং ফ্লোটিং-পয়েন্ট সংখ্যা পুরোপুরি বাদ দিয়ে কেবল ইমপ্লিসিট বৃত্তের সমীকরণ ও মিডপয়েন্ট বা মধ্যবিন্দুর অবস্থান পরীক্ষা করে পিক্সেল নির্বাচন করে।

ইমপ্লিসিট সার্কেল ফাংশন (Implicit Circle Function)

মূলবিন্দু $(0, 0)$-এ $R$ ব্যাসার্ধের বৃত্তের ইমপ্লিসিট ফাংশন $F(x, y)$ নিম্নরূপ:

$F(x, y) = x^2 + y^2 - R^2$

২ডি সমতলে অবস্থানরত যেকোনো বিন্দু $(x, y)$-এর জন্য $F(x, y)$-এর মান ৩টি অবস্থা নির্দেশ করে:

• $F(x, y) < 0$: বিন্দুটি বৃত্তের পরিধির ভেতরে অবস্থিত (মূলবিন্দু থেকে দূরত্ব $r < R$)।
• $F(x, y) = 0$: বিন্দুটি বৃত্তের পরিধির সরাসরি ওপর অবস্থিত (মূলবিন্দু থেকে দূরত্ব $r = R$)।
• $F(x, y) > 0$: বিন্দুটি বৃত্তের পরিধির বাইরে অবস্থিত (মূলবিন্দু থেকে দূরত্ব $r > R$)।

---

Decision Variable & Pixel Selection Rules (পিক্সেল নির্বাচনের নিয়ম)

দ্বিতীয় অকট্যান্টে ($0 \le x \le y$) বিন্দুটি $(0, R)$ থেকে ডান-নিচের দিকে অগ্রসর হয়। প্রতি ধাপে $x$-এর মান ১ বাড়িয়ে ($x_{k+1} = x_k + 1$) পরবর্তী পিক্সেল আঁকার সময় $y$-এর মান হয় একই থাকে, অথবা ১ কমে যায়।

বর্তমান পিক্সেল $P_k = (x_k, y_k)$ প্লট করার পর পরবর্তী ধাপের জন্য দুটি সম্ভাব্য ক্যান্ডিডেট পিক্সেল থাকে:

১. East ($E$): $(x_k + 1, y_k)$ ২. South-East ($SE$): $(x_k + 1, y_k - 1)$

মিডপয়েন্ট $M$ পরীক্ষা

$E$ নাকি $SE$ — কোন পিক্সেলটি বৃত্তের প্রকৃত চাপের বেশি কাছে অবস্থিত, তা নির্ধারণের জন্য $E$ ও $SE$-এর ঠিক মাঝের মিডপয়েন্ট $M$ পরীক্ষা করা হয়:

$M = \left(x_k + 1, y_k - \frac{1}{2}\right)$

মিডপয়েন্ট $M$-কে ইমপ্লিসিট বৃত্তের ফাংশনে বসালে সিদ্ধান্ত ভেরিয়েবল $p_k$ পাওয়া যায়:

$p_k = F(M) = F\left(x_k + 1, y_k - \frac{1}{2}\right) = (x_k + 1)^2 + \left(y_k - \frac{1}{2}\right)^2 - R^2$

পিক্সেল নির্বাচনের সিদ্ধান্ত নিয়ম

---

Incremental Decision Variable Updates & Initial Values (ইনক্রিমেন্টাল মান হিসাব)

প্রতি ধাপে শুরু থেকে $p_k = (x_k + 1)^2 + (y_k - 0.5)^2 - R^2$ গণনা করতে গেলে আবার গুণন চলে আসবে। তাই পূর্ববর্তী সিদ্ধান্ত মান $p_k$ থেকে ইনক্রিমেন্টালি (পর্যায়ক্রমিক যোগের মাধ্যমে) পরবর্তী $p_{k+1}$ বের করা হয়।

১. ইনক্রিমেন্টাল সমীকরণ প্রতিপাদন

পরবর্তী ধাপের সিদ্ধান্ত মান:

$p_{k+1} = F\left(x_{k+1} + 1, y_{k+1} - \frac{1}{2}\right) = (x_{k+1} + 1)^2 + \left(y_{k+1} - \frac{1}{2}\right)^2 - R^2$

$p_{k+1}$ থেকে $p_k$ বিয়োগ করলে পাই:

$p_{k+1} - p_k = (x_{k+1} + 1)^2 - (x_k + 1)^2 + \left(y_{k+1} - \frac{1}{2}\right)^2 - \left(y_k - \frac{1}{2}\right)^2$

যেহেতু $x_{k+1} = x_k + 1$, তাই $(x_{k+1} + 1)^2 - (x_k + 1)^2 = 2x_k + 3 = 2x_{k+1} + 1$।

কেস ১: East ($E$) পিক্সেল বেছে নিলে ($p_k < 0$)

এখানে $y_{k+1} = y_k$ (অর্থাৎ $y$ অপরিবর্তিত থাকে)। তাই $y$-এর পদগুলো কাটাকাটি চলে যায়:

$p_{k+1} = p_k + 2x_k + 3 = p_k + 2x_{k+1} + 1$

কেস ২: South-East ($SE$) পিক্সেল বেছে নিলে ($p_k \ge 0$)

এখানে $y_{k+1} = y_k - 1$ (অর্থাৎ $y$ ১ কমে)। বীজগাণিতিক সমাধান করলে পাওয়া যায়:

$p_{k+1} = p_k + 2x_k - 2y_k + 5 = p_k + 2x_{k+1} - 2y_{k+1} + 1$

২. প্রাথমিক মান ($p_0$) হিসাব

অ্যালগরিদম বৃত্তের শীর্ষবিন্দু থেকে কাজ শুরু করে:

$(x_0, y_0) = (0, R)$

প্রথম মিডপয়েন্ট $M_0$ এর স্থানাঙ্ক:

$M_0 = \left(1, R - \frac{1}{2}\right)$

$M_0$-কে $F(x, y)$-এ বসালে প্রাথমিক সিদ্ধান্ত মান $p_0$ পাওয়া যায়:

$p_0 = F\left(1, R - \frac{1}{2}\right) = 1^2 + \left(R - \frac{1}{2}\right)^2 - R^2$

$p_0 = 1 + R^2 - R + \frac{1}{4} - R^2 = \frac{5}{4} - R$

---

Mid-Point Circle Algorithm Step-by-Step & Pseudocode (সিউডোকোড)

নিচে ১০০% পূর্ণসংখ্যা নির্ভর মিডপয়েন্ট সার্কেল অ্যালগরিদমের সম্পূর্ণ সিউডোকোড ও ইনটিজার লজিক দেওয়া হলো।

স্ট্যান্ডার্ড সিউডোকোড

text

Copy

উদাহরণ ধাপে ধাপে ট্র্যাকিং ($R = 10$)

কেন্দ্র $(0, 0)$ এবং ব্যাসার্ধ $R = 10$-এর জন্য অ্যালগরিদম ট্র্যাকিং:

• প্রাথমিক অবস্থা: $x = 0, y = 10$, $p_0 = 1 - 10 = -9$।

---

University Exam Questions & Solutions (বিশ্ববিদ্যালয়ের সম্ভাব্য প্রশ্ন ও পূর্ণাঙ্গ সমাধান)

বিশ্ববিদ্যালয় সেমিস্টার পরীক্ষায় মিডপয়েন্ট সার্কেল অ্যালগরিদম থেকে প্রায়শই যেসব থিওরিটিক্যাল প্রশ্ন ও গাণিতিক সমস্যা আসে, সেগুলো নিচে বিস্তারিতভাবে আলোচনা করা হলো।

১. থিওরিটিক্যাল প্রশ্ন ও উত্তর (Theoretical Questions & Answers)

---

২. গাণিতিক সমস্যা ও পূর্ণাঙ্গ সমাধান (Step-by-Step Mathematical Problems)

সমস্যা ১: মূলবিন্দুতে কেন্দ্র এবং $R = 8$ ব্যাসার্ধবিশিষ্ট বৃত্ত

প্রশ্ন: মিডপয়েন্ট সার্কেল অ্যালগরিদম ব্যবহার করে কেন্দ্র $(0, 0)$ এবং ব্যাসার্ধ $R = 8$-এর জন্য প্রথম অকট্যান্টের পিক্সেলসমূহ নির্ণয় করো এবং একটি পূর্ণাঙ্গ টেবিল তৈরি করো।

সমাধান:

• প্রদত্ত: কেন্দ্র $(x_c, y_c) = (0, 0)$, ব্যাসার্ধ $R = 8$
• শুরুর বিন্দু: $(x_0, y_0) = (0, 8)$
• প্রাথমিক সিদ্ধান্ত ভেরিয়েবল: $p_0 = 1 - R = 1 - 8 = -7$

ইনক্রিমেন্টাল সূত্রসমূহ:

• যদি $p_k < 0$ হয় (East / $E$): $x_{k+1} = x_k + 1, \quad y_{k+1} = y_k$ $p_{k+1} = p_k + 2x_{k+1} + 1$
• যদি $p_k \ge 0$ হয় (South-East / $SE$): $x_{k+1} = x_k + 1, \quad y_{k+1} = y_k - 1$ $p_{k+1} = p_k + 2x_{k+1} - 2y_{k+1} + 1$

১ম অকট্যান্টে প্রাপ্ত পিক্সেলসমূহ: $(0, 8), (1, 8), (2, 8), (3, 7), (4, 7), (5, 6), (6, 5)$

৮-গুণ প্রতিসাম্য দ্বারা প্রতিটি বিন্দুর সমমিত ৮টি পিক্সেল:

• $(1, 8) \implies (1, 8), (-1, 8), (1, -8), (-1, -8), (8, 1), (-8, 1), (8, -1), (-8, -1)$
• $(2, 8) \implies (2, 8), (-2, 8), (2, -8), (-2, -8), (8, 2), (-8, 2), (8, -2), (-8, -2)$
• $(3, 7) \implies (3, 7), (-3, 7), (3, -7), (-3, -7), (7, 3), (-7, 3), (7, -3), (-7, -3)$
• $(4, 7) \implies (4, 7), (-4, 7), (4, -7), (-4, -7), (7, 4), (-7, 4), (7, -4), (-7, -4)$
• $(5, 6) \implies (5, 6), (-5, 6), (5, -6), (-5, -6), (6, 5), (-6, 5), (6, -5), (-6, -5)$

---

সমস্যা ২: স্থানান্তরিত কেন্দ্র $(x_c, y_c) = (5, 5)$ এবং $R = 6$

প্রশ্ন: কেন্দ্র $(5, 5)$ এবং ব্যাসার্ধ $R = 6$ বিশিষ্ট বৃত্তের প্রথম অকট্যান্টের পিক্সেল স্থানাঙ্ক এবং স্ক্রিনের মূল স্থানাঙ্ক নির্ণয় করো।

সমাধান:

• প্রদত্ত: $(x_c, y_c) = (5, 5), R = 6$
• প্রাথমিক বিন্দু (মূলবিন্দু সাপেক্ষে): $(x_0, y_0) = (0, 6)$
• প্রাথমিক সিদ্ধান্ত ভেরিয়েবল: $p_0 = 1 - R = 1 - 6 = -5$

স্ক্রিনে অঙ্কিত চূড়ান্ত পিক্সেলসমূহ (১ম অকট্যান্ট): $(5, 11), (6, 11), (7, 11), (8, 10), (9, 9)$

---

সমস্যা ৩: মিডপয়েন্ট সার্কেল অ্যালগরিদম প্রতিপাদন ও কেন্দ্র $(2, 2)$, ব্যাসার্ধ $R = 3$ বিশিষ্ট বৃত্ত অঙ্কন [১১তম ব্যাচ ফাইনাল পরীক্ষা (11th Batch)]

ধাপে ধাপে পরীক্ষার সমাধান:

১ম অংশ: মিডপয়েন্ট সার্কেল অ্যালগরিদমের প্রতিপাদন [৩.৫ নম্বর] ১. বৃত্তের ইমপ্লিসিট ফাংশন: মূলবিন্দুতে কেন্দ্র এবং $R$ ব্যাসার্ধের বৃত্তের সমীকরণ: $F(x, y) = x^2 + y^2 - R^2$

• $F(x, y) < 0 \implies$ বিন্দুটি বৃত্তের অভ্যন্তরে অবস্থিত।
• $F(x, y) = 0 \implies$ বিন্দুটি বৃত্তের পরিধির ওপর অবস্থিত।
• $F(x, y) > 0 \implies$ বিন্দুটি বৃত্তের বাইরে অবস্থিত।

২. মিডপয়েন্ট সিদ্ধান্ত গ্রহণ: ২য় অকট্যান্টে ($0 \le x \le y$) শীর্ষবিন্দু $(0, R)$ থেকে প্রতি ধাপে $x$ বরাবর ১ একক বৃদ্ধি পায়। দুটি সম্ভাব্য পিক্সেল হলো East $E(x_k + 1, y_k)$ এবং South-East $SE(x_k + 1, y_k - 1)$। এদের মধ্যবর্তী মিডপয়েন্ট: $M = \left(x_k + 1, \, y_k - \frac{1}{2}\right)$ সিদ্ধান্ত ভেরিয়েবল $p_k = F(M) = (x_k + 1)^2 + \left(y_k - \frac{1}{2}\right)^2 - R^2$।

৩. প্রাথমিক সিদ্ধান্ত প্যারামিটার ($p_0$): সূচনা বিন্দু $(x_0, y_0) = (0, R)$-এর জন্য: $p_0 = F\left(1, R - \frac{1}{2}\right) = 1^2 + \left(R - \frac{1}{2}\right)^2 - R^2 = \frac{5}{4} - R \approx \mathbf{1 - R}$

৪. ইনক্রিমেন্টাল সিদ্ধান্ত আপডেট:

• যদি $p_k < 0$ হয় ($E$ নির্বাচন): $y_{k+1} = y_k \implies p_{k+1} = p_k + 2x_{k+1} + 1$।
• যদি $p_k \ge 0$ হয় ($SE$ নির্বাচন): $y_{k+1} = y_k - 1 \implies p_{k+1} = p_k + 2x_{k+1} - 2y_{k+1} + 1$।

---

২য় অংশ: কেন্দ্র $(x_c, y_c) = (2, 2)$ এবং $R = 3$ এর গাণিতিক হিসাব ও চিত্রাঙ্কন [৩.৫ নম্বর]

১. প্রদত্ত উপাত্ত:

• কেন্দ্র: $(x_c, y_c) = (2, 2)$
• ব্যাসার্ধ: $R = 3$
• প্রারম্ভিক রিলেটিভ বিন্দু: $(x_0, y_0) = (0, 3)$
• প্রারম্ভিক স্ক্রিন পিক্সেল: $(x_0 + x_c, y_0 + y_c) = (0 + 2, 3 + 2) = \mathbf{(2, 5)}$
• প্রাথমিক সিদ্ধান্ত প্যারামিটার: $p_0 = 1 - R = 1 - 3 = \mathbf{-2}$

২. ধাপে ধাপে স্টেট ট্রেস সারণী:

৩. ২য় অকট্যান্টে প্রাপ্ত রিলেটিভ বিন্দুসমূহ: $(0, 3), \; (1, 3), \; (2, 2)$

৪. ৮-গুণ প্রতিসাম্য দ্বারা প্রাপ্ত সকল স্ক্রিন পিক্সেল (কেন্দ্র $(2, 2)$ সাপেক্ষে):

প্রতিটি রিলেটিভ $(x, y)$-এর জন্য স্ক্রিন স্থানাঙ্ক $(2 \pm x, 2 \pm y)$ এবং $(2 \pm y, 2 \pm x)$:

• $(0, 3)$ বিন্দু থেকে (৪টি অক্ষীয় বিন্দু): $(2, 5), \; (2, -1), \; (5, 2), \; (-1, 2)$
• $(1, 3)$ বিন্দু থেকে (৮টি প্রতিসম বিন্দু): $(3, 5), \; (1, 5), \; (3, -1), \; (1, -1), \; (5, 3), \; (-1, 3), \; (5, 1), \; (-1, 1)$
• $(2, 2)$ বিন্দু থেকে (৪টি কর্ণের বিন্দু): $(4, 4), \; (0, 4), \; (4, 0), \; (0, 0)$

৫. পিক্সেল গ্রিডে বৃত্তের চিত্রাঙ্কন:

---

৩. অনুশীলন সমস্যা ও পূর্ণাঙ্গ সমাধান (Practice Problems with Step-by-Step Solutions)

অনুশীলন ১: কেন্দ্র $(0, 0)$ এবং $R = 7$

প্রশ্ন: মিডপয়েন্ট সার্কেল অ্যালগরিদম ব্যবহার করে $R = 7$ ব্যাসার্ধের বৃত্তের জন্য সম্পূর্ণ ট্র্যাকিং টেবিল তৈরি করো।

সমাধান:

• $x_0 = 0, y_0 = 7, p_0 = 1 - 7 = -6$।
• ধাপ ০ ($p_0 = -6 < 0$): $E$ নির্বাচন $\implies (1, 7)$, $p_1 = -6 + 2(1) + 1 = -3$
• ধাপ ১ ($p_1 = -3 < 0$): $E$ নির্বাচন $\implies (2, 7)$, $p_2 = -3 + 2(2) + 1 = 2$
• ধাপ ২ ($p_2 = 2 \ge 0$): $SE$ নির্বাচন $\implies (3, 6)$, $p_3 = 2 + 2(3) - 2(6) + 1 = -3$
• ধাপ ৩ ($p_3 = -3 < 0$): $E$ নির্বাচন $\implies (4, 6)$, $p_4 = -3 + 2(4) + 1 = 6$
• ধাপ ৪ ($p_4 = 6 \ge 0$): $SE$ নির্বাচন $\implies (5, 5)$, $p_5 = 6 + 2(5) - 2(5) + 1 = 7$
• ধাপ ৫ ($x = y = 5$ এ এসে লুপ সমাপ্ত)।

১ম অকট্যান্টের পিক্সেল তালিকা: $(0, 7), (1, 7), (2, 7), (3, 6), (4, 6), (5, 5)$।

---

অনুশীলন ২: কেন্দ্র $(3, 4)$ এবং $R = 5$

প্রশ্ন: কেন্দ্র $(3, 4)$ এবং ব্যাসার্ধ $R = 5$ বিশিষ্ট বৃত্তের প্রতিটি ধাপের সিদ্ধান্ত মান এবং স্ক্রিন পিক্সেল দেখাও।

সমাধান:

• $p_0 = 1 - 5 = -4$, শুরু $(0, 5)$ $\to$ স্ক্রিন পিক্সেল $(3, 9)$।
• ধাপ ০ ($p_0 = -4 < 0$): $E \implies (1, 5) \to$ স্ক্রিন পিক্সেল $(4, 9)$, $p_1 = -4 + 2(1) + 1 = -1$।
• ধাপ ১ ($p_1 = -1 < 0$): $E \implies (2, 5) \to$ স্ক্রিন পিক্সেল $(5, 9)$, $p_2 = -1 + 2(2) + 1 = 4$।
• ধাপ ২ ($p_2 = 4 \ge 0$): $SE \implies (3, 4) \to$ স্ক্রিন পিক্সেল $(6, 8)$, $p_3 = 4 + 2(3) - 2(4) + 1 = 3$।
• ধাপ ৩ ($p_3 = 3 \ge 0$): $SE \implies (4, 3) \to$ যেহেতু $x > y$ ($4 > 3$), গণনা এখানে শেষ।

স্ক্রিন পিক্সেলসমূহ: $(3, 9), (4, 9), (5, 9), (6, 8), (7, 7)$।

---