Marching squares
कंप्यूटर ग्राफिक्स में, मार्चिंग स्क्वेयर्स एक एल्गोरिथ्म है जो दो आयामी स्केलर क्षेत्र (व्यक्तिगत संख्यात्मक मूल्यों की आयताकार सरणी) के लिए आकृति उत्पन्न करता है। इसी तरह की विधि का उपयोग 2डी त्रिभुज जाली को समोच्च बनाने के लिए किया जा सकता है। आकृति दो प्रकार की हो सकती हैः आइसोलिन-एक एकल डेटा स्तर के बाद की रेखाएँ, या आइसोवल्यू। आइसोबैंड्स-आइसोलेन्स के बीच भरे हुए क्षेत्र। विशिष्ट अनुप्रयोगों में स्थलाकृतिक मानचित्रों पर समोच्च रेखाएं या मौसम मानचित्रों के लिए समस्थानिकों की पीढ़ी शामिल हैं। मार्चिंग स्क्वेयर्स 3डी मार्चिंग क्यूब्स एल्गोरिदम के समान दृष्टिकोण अपनाते हैंः ग्रिड में प्रत्येक सेल को स्वतंत्र रूप से संसाधित करें। कोशिका कोनों पर डेटा मूल्यों के साथ समोच्च स्तर (ओं) की तुलना का उपयोग करके एक कोशिका सूचकांक की गणना करें। सेल के लिए आउटपुट ज्यामिति का वर्णन करने के लिए सेल सूचकांक पर कुंजीकृत एक पूर्व-निर्मित लुकअप टेबल का उपयोग करें। सटीक समोच्च स्थिति की गणना करने के लिए कोशिका की सीमाओं के साथ रैखिक अंतर्वेशन लागू करें। बुनियादी एल्गोरिथ्म यहाँ एल्गोरिथ्म के चरण हैंः द्विआधारी छवि बनाने के लिए 2डी क्षेत्र में एक सीमा लागू करें जिसमें शामिल हैंः 1 जहां डेटा मान समस्थानिक 0 से ऊपर है जहां डेटा मान समस्थानिक से नीचे है द्विआधारी छवि में पिक्सेल का हर 2x2 ब्लॉक एक समोच्च कोशिका बनाता है, इसलिए पूरी छवि को ऐसी कोशिकाओं के ग्रिड द्वारा दर्शाया जाता है (नीचे दिए गए चित्र में हरे रंग में दिखाया गया है)। ध्यान दें कि यह समोच्च ग्रिड मूल 2डी क्षेत्र की तुलना में प्रत्येक दिशा में एक सेल छोटा है। कंटूरिंग ग्रिड में प्रत्येक सेल के लिएः एक द्विआधारी सूचकांक बनाने के लिए सेल के कोनों पर 4 बिट लिखेंः सूचकांक में बिट को जोड़ते हुए घड़ी की दिशा में सेल के चारों ओर चलें, बिटवाइज ओआर और लेफ्ट-शिफ्ट का उपयोग करते हुए, सबसे महत्वपूर्ण बिट से ऊपर बाईं ओर, कम से कम नीचे बाईं ओर महत्वपूर्ण बिट। परिणामी 4-बिट सूचकांक की सीमा 0-15 में 16 संभावित मान हो सकते हैं। सेल का प्रतिनिधित्व करने के लिए आवश्यक किनारों को सूचीबद्ध करने वाली 16 प्रविष्टियों के साथ एक पूर्व-निर्मित खोज तालिका तक पहुँचने के लिए सेल सूचकांक का उपयोग करें (नीचे चित्र के निचले दाएँ भाग में दिखाया गया है)। कोशिका के किनारों के साथ समोच्च रेखा की सटीक स्थिति का पता लगाने के लिए मूल क्षेत्र डेटा मूल्यों के बीच रैखिक अंतर्वेशन लागू करें। काठी बिंदुओं का असंदिग्धता काठी बिंदुओं पर समोच्च अस्पष्ट है। अंतर्वेष्टित बिंदुओं के विभिन्न कनेक्शनों के बीच चयन करने के लिए कोशिका के केंद्र के लिए औसत डेटा मूल्य का उपयोग करके अस्पष्टता को हल करना संभव है (नीचे-दाएं कोने में चार चित्र): आइसोबैंड्स ऊपरी और निचले सीमा मूल्यों के भीतर भरे हुए समोच्च बैंड के लिए एक समान एल्गोरिथ्म बनाया जा सकता हैः समोच्च त्रिभुज जाली वही मूल एल्गोरिथ्म त्रिकोणीय जाली पर लागू किया जा सकता है, जिसमें शीर्षों को सौंपे गए डेटा के साथ जुड़े त्रिकोण होते हैं। उदाहरण के लिए, डेटा फ़ील्ड को समोच्च बनाने की अनुमति देने के लिए डेटा बिंदुओं के एक बिखरे हुए सेट को डेलाउने त्रिकोण के साथ जोड़ा जा सकता है। एक त्रिकोणीय कोशिका हमेशा समतलीय होती है, क्योंकि यह एक 2-सिम्प्लेक्स (अर्थात। एक एन-आयामी स्थान में एन + 1 शीर्षों द्वारा निर्दिष्ट)। एक त्रिभुज के पार हमेशा एक अद्वितीय रैखिक प्रक्षेपक होता है, और एक अस्पष्ट काठी की कोई संभावना नहीं होती है। समस्थानिक त्रिभुज पर समस्थानिकों के लिए विश्लेषण विशेष रूप से सरल हैः 3 द्विआधारी अंक हैं, इसलिए 8 संभावनाएं हैंः समस्थानिक त्रिभुज पर समस्थानिकों के लिए विश्लेषण के लिए 3 त्रिभुज त्रिटों की आवश्यकता होती है, इसलिए 27 संभावनाएं हैंः आयाम और स्थान मार्चिंग स्क्वेयर्स एल्गोरिथ्म के लिए डेटा स्थान 2डी है, क्योंकि डेटा मान सौंपे गए शीर्ष 2डी टोपोलॉजिकल ग्रिड में अपने पड़ोसियों से जुड़े होते हैं, लेकिन शीर्षों को सौंपे गए स्थानिक निर्देशांक 2डी, 3डी या उच्च आयामों में हो सकते हैं। उदाहरण के लिए, एक त्रिकोणीय जाल 3डी स्पेस में एम्बेडेड 2डी डेटा सतह का प्रतिनिधित्व कर सकता है, जहां एक समोच्च के साथ शीर्षों और प्रक्षेपित बिंदुओं की स्थानिक स्थिति में सभी में 3 निर्देशांक होंगे। ध्यान दें कि वर्गों का मामला फिर से अस्पष्ट है, क्योंकि 3-आयामी स्थान में अंतर्निहित एक चतुर्भुज आवश्यक रूप से समतल नहीं है, इसलिए 3डी में पट्टीदार सतहों को खींचने के लिए ज्यामितीय प्रक्षेप योजना का एक विकल्प है। प्रदर्शन पर विचार एल्गोरिथ्म शर्मनाक रूप से समानांतर है, क्योंकि सभी कोशिकाओं को स्वतंत्र रूप से संसाधित किया जाता है। यह मानते हुए एक समानांतर एल्गोरिथ्म लिखना आसान हैः साझा केवल-पढ़ने योग्य इनपुट स्केलर क्षेत्र। साझा परिशिष्ट-केवल ज्यामिति आउटपुट स्ट्रीम। प्रत्येक कोशिका को स्वतंत्र रूप से संसाधित करने वाले मार्चिंग स्क्वेयर्स का एक सरल कार्यान्वयन प्रत्येक रैखिक अंतर्वेशन को दो बार (आइसोलाइन) या चार बार (आइसोबैंड) करेगा। इसी तरह, आउटपुट में असंबद्ध रेखाओं (आइसोलाइन) के लिए 2डी शीर्षों की 2 प्रतियां या बहुभुज (आइसोबैंड) के लिए 4 प्रतियां होंगी। [इन धारणाओं के तहत किः ग्रिड बड़ा है, इसलिए अधिकांश कोशिकाएं आंतरिक हैं; और आइसोबैंड का एक पूर्ण सन्निहित सेट बनाया जा रहा है।] अंतर्वेशन के परिणामों को कैशिंग करके कम्प्यूटेशनल ओवरहेड को कम करना संभव है। उदाहरण के लिए, एक एकल-थ्रेडेड सीरियल संस्करण को केवल इनपुट ग्रिड की एक पंक्ति के लिए प्रक्षेपित परिणामों को कैश करने की आवश्यकता होगी। अनुक्रमित ज्यामितीय आदिम का उपयोग करके उत्पादन के आकार को कम करना भी संभव है, अर्थात। 2डी शीर्षों की एक सरणी बनाएँ और सरणी में छोटे पूर्णांक ऑफसेट के साथ रेखाओं या बहुभुज को निर्दिष्ट करें। संदर्भ बाहरी लिंक मार्चिंग स्क्वायर मैटलैब एल्गोरिथ्म-ओपन-सोर्स मार्चिंग स्क्वायर एल्गोरिथ्म को समझने में आसान। जावा में जावा मार्चिंग स्क्वेयर्स कोड में कार्यान्वयन। 2डी डेटा सेट और थ्रेसहोल्ड को देखते हुए, आसान प्लॉटिंग के लिए जनरलपाथ [] देता है। घुमावदार त्रिभुज व्याख्या और पायथन कार्यान्वयन का नमूना। सी में मार्चिंग स्क्वेयर्स कोड-मार्चिंग स्क्वेयर्स के लिए एक एकल हेडर लाइब्रेरी जो आसान प्रतिपादन के लिए त्रिभुज जाली का निर्यात कर सकती है। कंप्यूटर ग्राफिक्स एल्गोरिदम