Marching squares
کمپیوٹر گرافکس میں، مارچنگ اسکوائرز ایک الگورتھم ہے جو دو جہتی اسکیلر فیلڈ (انفرادی عددی اقدار کی آئتاکار صف) کے لیے شکل پیدا کرتا ہے۔ اسی طرح کا طریقہ 2 ڈی مثلث میش کو کونٹور کرنے کے لیے استعمال کیا جا سکتا ہے۔ شکل دو قسم کی ہو سکتی ہے: آئسولائنز-ایک ڈیٹا لیول کے بعد آنے والی لائنیں، یا آئسوولیو۔ آئسو بینڈز-آئسو لائنز کے درمیان بھرے ہوئے علاقے۔ عام ایپلی کیشنز میں ٹپوگرافک نقشوں پر کنٹور لائنیں یا موسمی نقشوں کے لیے آئسوبار کی نسل شامل ہیں۔ مارچنگ اسکوائرز تھری ڈی مارچنگ کیوب الگورتھم سے ملتا جلتا نقطہ نظر اختیار کرتے ہیں: گرڈ میں ہر سیل کو آزادانہ طور پر پروسیس کریں۔ سیل کونوں پر ڈیٹا ویلیوز کے ساتھ کونٹور لیول (سطحوں) کے موازنہ کا استعمال کرتے ہوئے سیل انڈیکس کا حساب لگائیں۔ سیل کے لیے آؤٹ پٹ جیومیٹری کو بیان کرنے کے لیے سیل انڈیکس پر کلیدی شکل میں پہلے سے تیار کردہ لک اپ ٹیبل کا استعمال کریں۔ عین مطابق کنٹور پوزیشن کا حساب لگانے کے لیے سیل کی حدود کے ساتھ لکیری انٹرپولیشن کا اطلاق کریں۔ بنیادی الگورتھم یہاں الگورتھم کے مراحل ہیں: بائنری امیج بنانے کے لیے 2D فیلڈ پر ایک حد لگائیں جس میں: 1 جہاں ڈیٹا ویلیو آئسوولیو 0 سے اوپر ہے جہاں ڈیٹا ویلیو آئسوولیو سے نیچے ہے۔ بائنری امیج میں پکسلز کا ہر 2x2 بلاک ایک کنٹورنگ سیل بناتا ہے، لہذا پوری امیج کی نمائندگی ایسے خلیوں کے گرڈ سے کی جاتی ہے (نیچے دی گئی تصویر میں سبز رنگ میں دکھایا گیا ہے)۔ نوٹ کریں کہ یہ کنٹورنگ گرڈ اصل 2 ڈی فیلڈ کے مقابلے میں ہر سمت میں ایک سیل چھوٹا ہے۔ کنٹورنگ گرڈ کے ہر خلیے کے لیے: بائنری انڈیکس بنانے کے لیے خلیے کے کونوں پر 4 بٹس مرتب کریں: خلیے کے گرد گھڑی کی سمت چلیں، بٹ کو انڈیکس میں جوڑتے ہوئے، بٹ وائز OR اور لیفٹ شفٹ کا استعمال کرتے ہوئے، سب سے اہم بٹ سے اوپر بائیں طرف، کم از کم نیچے بائیں طرف اہم بٹ تک۔ نتیجے میں 4 بٹ انڈیکس کی حد 0-15 میں 16 ممکنہ اقدار ہو سکتی ہیں۔ سیل کی نمائندگی کرنے کے لیے درکار کناروں کی فہرست والے 16 اندراجات کے ساتھ پہلے سے تیار کردہ لک اپ ٹیبل تک رسائی حاصل کرنے کے لیے سیل انڈیکس کا استعمال کریں (نیچے تصویر کے نچلے دائیں حصے میں دکھایا گیا ہے)۔ سیل کے کناروں کے ساتھ کنٹور لائن کی صحیح پوزیشن تلاش کرنے کے لیے اصل فیلڈ ڈیٹا ویلیوز کے درمیان لکیری انٹرپولیشن کا اطلاق کریں۔ سیڈل پوائنٹس کی مبہم شکل سیڈل پوائنٹس پر مبہم ہے۔ خلیات کے مرکز کے لیے اوسط ڈیٹا ویلیو کا استعمال کرتے ہوئے انٹرپولیٹڈ پوائنٹس کے مختلف کنکشنز (نیچے دائیں کونے میں چار تصاویر) کے درمیان انتخاب کرکے ابہام کو حل کرنا ممکن ہے: آئسو بینڈز اوپری اور نچلی دہلیز ویلیوز کے اندر بھرے ہوئے کونٹور بینڈ کے لیے اسی طرح کا الگورتھم بنایا جا سکتا ہے: کونٹورنگ ٹرائنگل میش وہی بنیادی الگورتھم مثلث میش پر لاگو کیا جا سکتا ہے، جو عمودی حصوں کو تفویض کردہ ڈیٹا کے ساتھ منسلک مثلث پر مشتمل ہوتا ہے۔ مثال کے طور پر، ڈیٹا پوائنٹس کے بکھرے ہوئے سیٹ کو ڈیلونی مثلث کے ساتھ جوڑا جا سکتا ہے تاکہ ڈیٹا فیلڈ کو کنٹور کیا جا سکے۔ ایک سہ رخی خلیہ ہمیشہ ہموار ہوتا ہے، کیونکہ یہ ایک 2-سمپلیکس ہے (یعنی۔ n جہتی جگہ میں n + 1 عمودی طرف سے متعین)۔ مثلث کے پار ہمیشہ ایک منفرد لکیری انٹرپولینٹ ہوتا ہے، اور مبہم سیڈل کا کوئی امکان نہیں ہوتا ہے۔ آئسو لائنز مثلثوں پر آئسو لائنز کا تجزیہ خاص طور پر آسان ہے: 3 بائنری ہندسوں ہیں، لہذا 8 امکانات ہیں: آئسو بینڈز مثلثوں پر آئسو بینڈز کے تجزیے کے لیے 3 سہ رخی ٹریٹس کی ضرورت ہوتی ہے، لہذا 27 امکانات ہیں: طول و عرض اور خالی جگہیں مارچنگ اسکوائرز الگورتھم کے لیے ڈیٹا اسپیس 2 ڈی ہے، کیونکہ ڈیٹا ویلیو تفویض کردہ عمودی حصے 2 ڈی ٹوپولوجیکل گرڈ میں اپنے پڑوسیوں سے جڑے ہوتے ہیں، لیکن عمودی حصوں کو تفویض کردہ مقامی نقاط 2 ڈی، 3 ڈی یا اس سے زیادہ طول و عرض میں ہو سکتے ہیں۔ مثال کے طور پر، ایک سہ رخی میش تھری ڈی اسپیس میں سرایت شدہ 2 ڈی ڈیٹا کی سطح کی نمائندگی کر سکتا ہے، جہاں کونٹور کے ساتھ عمودی اور انٹرپولیٹڈ پوائنٹس کی مقامی پوزیشنوں میں 3 نقاط ہوں گے۔ نوٹ کریں کہ مربعوں کا معاملہ ایک بار پھر مبہم ہے، کیونکہ 3 جہتی جگہ میں سرایت شدہ ایک چوتھائی لازمی طور پر طیارہ نہیں ہے، لہذا 3D میں بینڈڈ سطحوں کو کھینچنے کے لیے ہندسی انٹرپولیشن اسکیم کا انتخاب ہے۔ کارکردگی کے تحفظات الگورتھم شرمناک طور پر متوازی ہے، کیونکہ تمام خلیوں پر آزادانہ طور پر کارروائی کی جاتی ہے۔ متوازی الگورتھم کو یہ فرض کرتے ہوئے لکھنا آسان ہے کہ: مشترکہ صرف پڑھنے کے لیے ان پٹ اسکیلر فیلڈ۔ مشترکہ صرف ضمیمہ جیومیٹری آؤٹ پٹ اسٹریم۔ مارچنگ اسکوائرز کا ایک بے وقوف نفاذ جو ہر خلیے کو آزادانہ طور پر پروسیس کرتا ہے، ہر لکیری انٹرپولیشن کو دو بار (آئسولین) یا چار بار (آئسو بینڈ) انجام دے گا۔ اسی طرح، آؤٹ پٹ میں جداگانہ لائنوں (آئسو لائن) کے لیے 2 ڈی عمودی کی 2 کاپیاں یا کثیر الاضحی (آئسو بینڈ) کے لیے 4 کاپیاں ہوں گی۔ [ان مفروضوں کے تحت کہ: گرڈ بڑا ہے، تاکہ زیادہ تر خلیے اندرونی ہوں ؛ اور آئسو بینڈ کا ایک مکمل ملحقہ مجموعہ بنایا جا رہا ہے۔] انٹرپولیشن کے نتائج کو کیش کرکے کمپیوٹیشنل اوور ہیڈ کو کم کرنا ممکن ہے۔ مثال کے طور پر، ایک تھریڈ والے سیریل ورژن کو صرف ان پٹ گرڈ کی ایک قطار کے لیے انٹرپولیٹڈ نتائج کیش کرنے کی ضرورت ہوگی۔ انڈیکسڈ جیومیٹرک پرائمیٹیوز کا استعمال کرکے آؤٹ پٹ کے سائز کو کم کرنا بھی ممکن ہے، یعنی۔ 2 ڈی عمودی کی ایک صف بنائیں اور صف میں مختصر عدد آفسیٹ کے ساتھ لکیروں یا کثیر الاضحی کی وضاحت کریں۔ حوالہ جات بیرونی روابط مارچنگ اسکوائر میٹ لیب الگورتھم-اوپن سورس مارچنگ اسکوائر الگورتھم کو سمجھنے میں آسان۔ جاوا میں جاوا مارچنگ اسکوائرز کوڈ میں نفاذ۔ 2 ڈی ڈیٹا سیٹ اور حد کو دیکھتے ہوئے، آسان پلاٹنگ کے لیے جنرل پتھ [] واپس کرتا ہے۔ مڑے ہوئے مثلث کی وضاحت اور ازگر کے نفاذ کا نمونہ۔ سی میں مارچنگ اسکوائرز کوڈ-مارچنگ اسکوائرز کے لیے ایک واحد ہیڈر لائبریری جو آسان انجام کے لیے مثلث میش برآمد کر سکتی ہے۔ کمپیوٹر گرافکس الگورتھم