Midpoint circle algorithm
کمپیوٹر گرافکس میں، مڈپوائنٹ سرکل الگورتھم ایک الگورتھم ہے جو دائرے کو رسٹرائز کرنے کے لیے درکار پوائنٹس کا تعین کرنے کے لیے استعمال ہوتا ہے۔ یہ بریسنھم کے لائن الگورتھم کی عمومی شکل ہے۔ الگورتھم کو کونک حصوں میں مزید عام کیا جا سکتا ہے۔ اور وان اکین۔ مشینی (سی این سی) میں، اسے سرکلر انٹرپولیشن کے نام سے جانا جاتا ہے۔ خلاصہ یہ الگورتھم تمام آٹھ آکٹینٹس کو بیک وقت کھینچتا ہے، جو ہر بنیادی سمت (0°، 90°، 180°، 270°) سے شروع ہوتا ہے اور 45° (45°، 135°، 225°، 325°) کے قریب ترین ضرب تک پہنچنے کے لیے دونوں طریقوں کو پھیلاتا ہے۔ یہ اس بات کا تعین کر سکتا ہے کہ کہاں رکنا ہے کیونکہ کب =، یہ 45° تک پہنچ چکا ہے۔ ان زاویوں کو استعمال کرنے کی وجہ مندرجہ بالا تصویر میں دکھائی گئی ہے: جیسے جیسے اضافہ ہوتا ہے، یہ 45° تک پہنچنے تک کسی قدر کو نہیں چھوڑتا اور نہ ہی دہراتا ہے۔ لہذا وائل لوپ کے دوران، ہر تکرار میں 1 کا اضافہ ہوتا ہے، اور موقع پر 1 کا کمی، ایک تکرار میں کبھی بھی 1 سے زیادہ نہیں ہوتا ہے۔ یہ 45° پر تبدیل ہوتا ہے کیونکہ یہی وہ نقطہ ہے جہاں ٹینجینٹ اٹھتا ہے = دوڑتا ہے۔ جبکہ اٹھو> پہلے دوڑو اور اٹھو <پیچھے دوڑو۔ مسئلہ کا دوسرا حصہ، فیصلہ کن، کہیں زیادہ مشکل ہے۔ یہ اس بات کا تعین کرتا ہے کہ کب کمی کرنی ہے۔ یہ عام طور پر ہر تکرار میں پکسلز کھینچنے کے بعد آتا ہے، کیونکہ یہ کبھی بھی پہلے پکسل کے رداس سے نیچے نہیں جاتا ہے۔ کیونکہ ایک مسلسل فنکشن میں، ایک دائرے کے لیے فنکشن ایک دائرے کے لیے فنکشن ہے جس کے رداس پر منحصر ہے (یا جو بھی تیسرا متغیر ہے)، اس کی وجہ یہ ہے کہ ایک مجرد (ووکسیل) دائرے کے لیے الگورتھم بھی اس پر انحصار کرے گا۔ مڈپوائنٹ سرکل الگورتھم۔ لیکن جب کسی دائرے کو دیکھتے ہیں تو، کچھ ملحقہ حلقوں کا عدد رداس ایک جیسا ہوتا ہے، لیکن اس سے توقع نہیں کی جاتی ہے کہ اسی نصف کرہ میں خود سے متصل ایک ہی درست دائرہ ہو۔ اس کے بجائے، ایک ہی رداس کے دائرے کو ایک مختلف تعین کنندہ کی ضرورت ہوتی ہے، تاکہ منحنی خطوط مرکز کے قدرے قریب آ سکیں یا آگے بڑھ سکیں۔ الگورتھم الگورتھم کا مقصد پکسلز کا استعمال کرتے ہوئے منحنی خطوط کا تخمینہ لگانا ہے۔ عام آدمی کے لحاظ سے ہر پکسل مرکز سے تقریبا ایک ہی فاصلے پر ہونا چاہیے۔ ہر مرحلے پر، ملحقہ پکسل کا انتخاب کرکے راستہ بڑھایا جاتا ہے جو مطمئن ہوتا ہے لیکن زیادہ سے زیادہ ہوتا ہے۔ چونکہ امیدوار پکسلز ملحقہ ہیں، مؤخر الذکر کے اظہار کا حساب لگانے کے لیے ریاضی کو آسان بنایا گیا ہے، جس میں صرف بٹ شفٹ اور اضافے کی ضرورت ہوتی ہے۔ لیکن بٹس شفٹ کو سمجھنے کے لیے ایک آسان کاری کی جا سکتی ہے۔ ذہن میں رکھیں کہ بائنری نمبر کی بائیں طرف کی بٹ شفٹ 2 کے ساتھ ضرب دینے کے برابر ہے۔ ارگو، رداس کی بائیں طرف کی بٹ شفٹ صرف قطر پیدا کرتی ہے جس کی تعریف رداس گنا دو کے طور پر کی جاتی ہے۔ یہ الگورتھم دائرے کی مساوات سے شروع ہوتا ہے۔ سادگی کے لیے فرض کریں کہ دائرے کا مرکز ہے۔ پہلے صرف پہلے آکٹینٹ پر غور کریں، اور ایک منحنی خطوط کھینچیں جو نقطہ پر شروع ہوتا ہے اور 45 کے زاویے تک پہنچ کر گھڑی کی مخالف سمت میں آگے بڑھتا ہے۔ یہاں تیز سمت (قیمت میں زیادہ اضافے کے ساتھ بیس ویکٹر) سمت ہے۔ الگورتھم ہمیشہ مثبت سمت (اوپر کی طرف) میں ایک قدم اٹھاتا ہے، اور کبھی کبھار سست سمت (منفی سمت) میں ایک قدم اٹھاتا ہے۔ دائرے کی مساوات سے تبدیل شدہ مساوات حاصل کی جاتی ہے، جہاں ابتدا کے دوران صرف ایک بار شمار کیا جاتا ہے۔ دائرے پر موجود پوائنٹس کو نقطہ پر ویکٹر کے نقاط کی ترتیب ہونے دیں (معمول کی بنیاد پر)۔ پوائنٹس کو اس ترتیب کے مطابق نمبر دیا جاتا ہے جس میں پہلے پوائنٹ کو تفویض کیا جاتا ہے۔ ہر پوائنٹ کے لیے، مندرجہ ذیل ہولڈز: اسے اس طرح دوبارہ ترتیب دیا جا سکتا ہے: اور اسی طرح اگلے پوائنٹ کے لیے: چونکہ پہلے آکٹینٹ کے لیے اگلا پوائنٹ ہمیشہ آخری سے کم از کم 1 پکسل زیادہ ہوگا (لیکن تسلسل کو برقرار رکھنے کے لیے زیادہ سے زیادہ 1 پکسل زیادہ بھی)، یہ سچ ہے کہ: لہذا، اگلے پوائنٹ مساوات کو متبادل بنا کر ایک ریکرسو میں دوبارہ کام کریں: ایک دائرے کے تسلسل کی وجہ سے اور کیونکہ دونوں محوروں کے ساتھ زیادہ سے زیادہ ایک ہی ہے، واضح طور پر یہ سکپنگ پوائنٹس نہیں ہوگا کیونکہ یہ ترتیب میں آگے بڑھتا ہے۔ عام طور پر یہ ایک ہی کوآرڈینیٹ پر رہتا ہے، اور بعض اوقات ایک سے آگے بڑھ جاتا ہے۔ اس کے نتیجے میں آنے والے کوآرڈینیٹ کا ترجمہ وسط نقطہ کوآرڈینیٹ شامل کرکے کیا جاتا ہے۔ یہ بار بار ہونے والے عدد کے اضافے کارکردگی کو زیادہ محدود نہیں کرتے، کیونکہ ان مربع (جڑ) کے حسابات کو باری باری اندرونی لوپ میں چھوڑا جا سکتا ہے۔ ایک بار پھر، تبدیل شدہ دائرے کی مساوات میں صفر کی جگہ غلطی کی اصطلاح لے لیتی ہے۔ غلطی کی اصطلاح کا آغاز شروع میں 1⁄2 پکسل کے آفسیٹ سے اخذ کیا گیا ہے۔ پرپینڈکولر لائن کے ساتھ انٹرسیکشن تک، یہ ایرر ٹرم میں جمع شدہ ویلیو کی طرف جاتا ہے، تاکہ یہ ویلیو ابتداء کے لیے استعمال ہو۔ دائرے کی مساوات، مثلثی تاثرات اور مربع جڑوں میں مربعوں کی بار بار ہونے والی گنتی سے ایک بار پھر ہر چیز کو ایک ہی مرحلے میں تحلیل کرکے اور سابقہ تکرار سے کواڈریٹک اصطلاحات کی تکراری گنتی کا استعمال کرکے بچا جا سکتا ہے۔ انٹیجر پر مبنی ریاضی کے ساتھ متغیر بالکل اسی طرح جیسے بریسنھم کے لائن الگورتھم کے ساتھ، اس الگورتھم کو انٹیجر پر مبنی ریاضی کے لیے بہتر بنایا جا سکتا ہے۔ سمیٹری کی وجہ سے، اگر کوئی الگورتھم پایا جا سکتا ہے جو صرف ایک آکٹینٹ کے لیے پکسلز کا حساب لگاتا ہے، تو پکسلز کو پورے دائرے کو حاصل کرنے کے لیے ظاہر کیا جا سکتا ہے۔ ہم رداس ایرر کو دائرے کی صحیح نمائندگی اور ہر پکسل کے مرکز کے نقطہ کے درمیان فرق کے طور پر بیان کرتے ہوئے شروع کرتے ہیں (یا پکسل پر کوئی دوسرا صوابدیدی ریاضیاتی نقطہ، جب تک کہ یہ تمام پکسلز میں مستقل ہو)۔ مرکز کے ساتھ کسی بھی پکسل کے لیے، رداس ایرر کی تعریف اس طرح کی جاتی ہے: وضاحت کے لیے، دائرے کے لیے یہ فارمولا اصل پر اخذ کیا جاتا ہے، لیکن الگورتھم کو کسی بھی مقام کے لیے تبدیل کیا جا سکتا ہے۔ مثبت ایکس محور پر نقطہ کے ساتھ شروع کرنا مفید ہے۔ کیونکہ رداس پکسلز کی ایک پوری تعداد ہوگی، واضح طور پر رداس کی غلطی صفر ہوگی: کیونکہ یہ پہلے گھڑی کی مخالف سمت مثبت آکٹینٹ سے شروع ہوتا ہے، یہ سب سے بڑے سفر، Y سمت کے ساتھ سمت میں قدم رکھے گا، لہذا یہ واضح ہے کہ۔ نیز، کیونکہ اس کا تعلق صرف اس آکٹینٹ سے ہے، اقدار کے پاس صرف 2 آپشن ہیں: سابقہ تکرار کی طرح ہی رہنا، یا 1 سے کم کرنا۔ ایک فیصلہ متغیر بنایا جا سکتا ہے جو اس بات کا تعین کرتا ہے کہ آیا مندرجہ ذیل درست ہے: اگر یہ عدم مساوات برقرار ہے، تو پلاٹ کریں ؛ اگر نہیں، تو پلاٹ کریں۔ تو، اس بات کا تعین کیسے کیا جائے کہ آیا یہ عدم مساوات برقرار ہے؟ رداس ایرر کی تعریف کے ساتھ شروع کریں: مطلق ویلیو فنکشن مدد نہیں کرتا ہے، لہذا دونوں اطراف مربع کریں، کیونکہ ایک مربع ہمیشہ مثبت ہوتا ہے: چونکہ> 0، اصطلاح، اس لیے تقسیم ہوتی ہے: اس طرح، فیصلہ کا معیار فلوٹنگ پوائنٹ آپریشنز کے استعمال سے سادہ انٹیجر ایڈیشن، گھٹاؤ، اور بٹ شفٹنگ (2 آپریشنز سے ضرب کے لیے) میں بدل جاتا ہے۔ اگر، تو قیمت کو کم کریں۔ اگر، تو وہی قیمت رکھیں۔ ایک بار پھر، تمام آکٹینٹس میں ان نکات کی عکاسی کرنے سے، ایک مکمل دائرہ کا نتیجہ نکلتا ہے۔ ہم اس فیصلہ فارمولے کی اقدار کے درمیان ڈیلٹا کا حساب صرف پچھلے مرحلے میں اس کی قیمت سے لگا کر حساب کو کم کر سکتے ہیں۔ ہم اس طرح تفویض کرنے سے شروع کرتے ہیں کہ فارمولے کی ابتدائی قیمت کون سی ہے، پھر ہر مرحلے پر اوپر کی طرح اگر ہم اسے (اور کمی) کے طور پر اپ ڈیٹ کرتے ہیں، بصورت دیگر وہاں سے معمول کے مطابق اضافہ ہوتا ہے۔ جیسکو کا طریقہ الگورتھم کو پہلے ہی کافی حد تک سمجھایا جا چکا ہے، لیکن مزید اصلاحات موجود ہیں۔ نیا پیش کردہ طریقہ فی قدم (8 پکسلز کے لیے) صرف 5 ریاضی کی کارروائیوں کے ساتھ ملتا ہے اور اس طرح صرف کم کارکردگی والے نظاموں کے لیے بہترین موزوں ہے۔ "اگر" آپریشن میں، صرف نشان چیک کیا جاتا ہے (مثبت؟ ہاں یا نہیں) اور ایک متغیر تفویض ہے، جسے ریاضی کا عمل بھی نہیں سمجھا جاتا ہے۔ پہلی لائن میں شروعات (4 بٹس سے دائیں طرف منتقل ہونا) صرف خوبصورتی کی وجہ سے ہے اور واقعی ضروری نہیں ہے۔ لہذا ہمیں مین لوپ کے اندر قابل گنتی کارروائیاں ملتی ہیں: موازنہ x> = y (سبسٹریکشن کے طور پر شمار کیا جاتا ہے: x-y> = 0) y = y + 1 [y + +] t1 + y t1-x موازنہ t2> = 0 شمار نہیں کیا جاتا ہے کیونکہ کوئی حقیقی ریاضی نہیں ہوتی ہے۔ دو کی تکمیل میں برتنوں کی نمائندگی میں صرف سائن بٹ کو چیک کرنا پڑتا ہے۔ x = x-1 [x--] آپریشنز: 5 t1 = r/16 x = r y = 0 دہرائیں جب تک کہ x <y پکسل (x, y) اور تمام سمیٹرک پکسلز رنگین نہ ہوں (8 بار) y = y + 1 t1 = t1 + y t2 = t1-x اگر t2> = 0 t1 = t2 x = x-1 نامکمل آکٹینٹس کھینچتے ہوئے اوپر کے نفاذ ہمیشہ صرف مکمل آکٹینٹس یا حلقے کھینچتے ہیں۔ زاویے سے زاویے تک صرف ایک مخصوص آرک کھینچنے کے لیے، الگورتھم کو پہلے ان اختتامی نکات کے نقاط اور نقاط کا حساب لگانے کی ضرورت ہوتی ہے، جہاں مثلثی یا مربع جڑ کے حسابات کا سہارا لینا ضروری ہے (مربع جڑوں کی کمپیوٹنگ کے طریقے دیکھیں)۔ پھر بریسنھم الگورتھم کو مکمل آکٹینٹ یا دائرے پر چلایا جاتا ہے اور پکسلز کو صرف اس صورت میں سیٹ کرتا ہے جب وہ مطلوبہ وقفے میں آتے ہیں۔ اس آرک کو ختم کرنے کے بعد، الگورتھم کو قبل از وقت ختم کیا جا سکتا ہے۔ اگر زاویہ ڈھلوانوں کے طور پر دیے گئے ہیں، تو کوئی مثلث یا مربع جڑیں ضروری نہیں ہیں: بس چیک کریں کہ مطلوبہ ڈھلوانوں کے درمیان ہے۔ عامیاں پیرابولہ، ایلیپس، یا کسی دوسرے دو جہتی منحنی خطوط کو رسٹرائز کرنے کے لیے بھی اسی تصور کو استعمال کرنا ممکن ہے۔ حوالہ جات بیرونی روابط دائرے کھینچنا-ڈرائنگ حلقوں پر ایک مضمون، جو ایک سادہ اسکیم سے لے کر متعدد پروگرامنگ زبانوں میں ایک موثر مڈپوائنٹ سرکل الگورتھم تک ماخوذ ہے۔ جیومیٹرک الگورتھم ڈیجیٹل جیومیٹری ڈی: راسٹرونگ وان Kreisen#Midpoint-الگورتھم