Marching squares
કોમ્પ્યુટર ગ્રાફિક્સમાં, કૂચ ચોરસ એ એક અલ્ગોરિધમ છે જે દ્વિ-પરિમાણીય સ્કેલર ક્ષેત્ર (વ્યક્તિગત આંકડાકીય મૂલ્યોની લંબચોરસ શ્રેણી) માટે રૂપરેખા પેદા કરે છે. આવી જ પદ્ધતિનો ઉપયોગ 2D ત્રિકોણ જાળીઓને સમોચ્ચ બનાવવા માટે કરી શકાય છે. રૂપરેખાઓ બે પ્રકારની હોઈ શકે છેઃ આઇસોલાઈન્સ-એક જ ડેટા સ્તરને અનુસરતી રેખાઓ, અથવા આઇસોવલ્યુ. આઇસોબેન્ડ્સ-આઇસોલેન્સ વચ્ચેના ભરેલા વિસ્તારો. લાક્ષણિક ઉપયોગોમાં ભૌગોલિક નકશા પર સમોચ્ચ રેખાઓ અથવા હવામાન નકશા માટે આઇસોબારની પેઢીનો સમાવેશ થાય છે. માર્ચિંગ સ્ક્વેર 3ડી માર્ચિંગ ક્યુબ્સ અલ્ગોરિધમનો સમાન અભિગમ અપનાવે છેઃ ગ્રીડમાં દરેક કોષ પર સ્વતંત્ર રીતે પ્રક્રિયા કરો. કોષના ખૂણાઓ પરના ડેટા મૂલ્યો સાથે સમોચ્ચ સ્તર (ઓ) ની સરખામણીનો ઉપયોગ કરીને કોષ અનુક્રમણિકાની ગણતરી કરો. સેલ માટે આઉટપુટ ભૂમિતિને વર્ણવવા માટે સેલ અનુક્રમણિકા પર કી કરેલ પૂર્વ-નિર્મિત લુકઅપ ટેબલનો ઉપયોગ કરો. ચોક્કસ સમોચ્ચ સ્થિતિની ગણતરી કરવા માટે કોષની સીમાઓ સાથે રેખીય પ્રક્ષેપણ લાગુ કરો. મૂળભૂત અલ્ગોરિધમ અહીં અલ્ગોરિધમના પગલાંઓ છેઃ દ્વિસંગી છબી બનાવવા માટે 2D ક્ષેત્રમાં એક થ્રેશોલ્ડ લાગુ કરો જેમાં નીચેનાનો સમાવેશ થાય છેઃ 1 જ્યાં ડેટા મૂલ્ય સમસ્થાનિક 0 ની ઉપર હોય છે જ્યાં ડેટા મૂલ્ય સમસ્થાનિકની નીચે હોય છે દ્વિસંગી છબીમાં પિક્સેલ્સનો દરેક 2x2 બ્લોક સમોચ્ચ કોષ બનાવે છે, તેથી સમગ્ર છબી આવા કોષોના ગ્રીડ દ્વારા રજૂ થાય છે (નીચે ચિત્રમાં લીલા રંગમાં બતાવેલ છે). નોંધ લો કે આ સમોચ્ચ ગ્રીડ મૂળ 2D ક્ષેત્ર કરતાં દરેક દિશામાં એક કોષ નાનો છે. સમોચ્ચ ગ્રીડમાં દરેક કોષ માટેઃ દ્વિસંગી અનુક્રમણિકા બનાવવા માટે કોષના ખૂણાઓ પર 4 બિટ્સ બનાવોઃ સૂચકાંકોમાં બીટને જોડીને ઘડિયાળની દિશામાં કોષની આસપાસ ચાલો, બિટવાઇઝ OR અને ડાબી-શિફ્ટનો ઉપયોગ કરીને, ઉપરની ડાબી બાજુએ સૌથી નોંધપાત્ર બીટથી, નીચે ડાબી બાજુએ ઓછામાં ઓછું નોંધપાત્ર બીટ. પરિણામી 4-બીટ અનુક્રમણિકામાં 0-15 શ્રેણીમાં 16 સંભવિત મૂલ્યો હોઈ શકે છે. સેલનું પ્રતિનિધિત્વ કરવા માટે જરૂરી ધારની યાદી ધરાવતી 16 એન્ટ્રીઓ સાથે પૂર્વ-નિર્મિત લુકઅપ ટેબલને ઍક્સેસ કરવા માટે સેલ અનુક્રમણિકાનો ઉપયોગ કરો (નીચે ચિત્રના નીચલા જમણા ભાગમાં બતાવેલ છે). કોષની ધાર પર સમોચ્ચ રેખાનું ચોક્કસ સ્થાન શોધવા માટે મૂળ ક્ષેત્ર ડેટા મૂલ્યો વચ્ચે રેખીય પ્રક્ષેપણ લાગુ કરો. કાઠી બિંદુઓની અસ્પષ્ટતા કાઠી બિંદુઓ પર સમોચ્ચ અસ્પષ્ટ છે. અંતર્વેષ્ટિત બિંદુઓના વિવિધ જોડાણો (નીચે-જમણા ખૂણામાં ચાર છબીઓ) વચ્ચે પસંદગી કરવા માટે કોષના કેન્દ્ર માટે સરેરાશ ડેટા મૂલ્યનો ઉપયોગ કરીને અસ્પષ્ટતાને ઉકેલવી શક્ય છેઃ આઇસોબેન્ડ્સ ઉપલા અને નીચલા થ્રેશોલ્ડ મૂલ્યોમાં ભરેલા સમોચ્ચ બેન્ડ માટે સમાન અલ્ગોરિધમ બનાવી શકાય છેઃ સમોચ્ચ ત્રિકોણ મેશ સમાન મૂળભૂત અલ્ગોરિધમ ત્રિકોણાકાર મેશ પર લાગુ કરી શકાય છે, જેમાં શિરોબિંદુઓને સોંપેલ ડેટા સાથે જોડાયેલા ત્રિકોણ હોય છે. ઉદાહરણ તરીકે, ડેટા ક્ષેત્રને સમોચ્ચ બનાવવાની મંજૂરી આપવા માટે ડેટા બિંદુઓના વેરવિખેર સમૂહને ડેલાઉને ત્રિકોણ સાથે જોડી શકાય છે. ત્રિકોણાકાર કોષ હંમેશા સમતલીય હોય છે, કારણ કે તે 2-સિમ્પ્લેક્સ (એટલે કે. n-પરિમાણીય અવકાશમાં n + 1 શિરોબિંદુઓ દ્વારા નિર્દિષ્ટ). ત્રિકોણમાં હંમેશા એક અનન્ય રેખીય અંતર્વેશક હોય છે, અને અસ્પષ્ટ કાઠીની કોઈ શક્યતા નથી. આઇસોલાઈન્સ ત્રિકોણ પર આઇસોલાઈન્સ માટેનું વિશ્લેષણ ખાસ કરીને સરળ છેઃ ત્યાં 3 દ્વિસંગી અંકો છે, તેથી ત્યાં 8 શક્યતાઓ છેઃ આઇસોબેન્ડ્સ ત્રિકોણ પર આઇસોબેન્ડ્સ માટેના વિશ્લેષણ માટે 3 ત્રિમાસિક ટ્રિટ્સની જરૂર છે, તેથી 27 શક્યતાઓ છેઃ પરિમાણો અને જગ્યાઓ માર્ચિંગ સ્ક્વેર્સ અલ્ગોરિધમ માટે ડેટા સ્પેસ 2D છે, કારણ કે ડેટા મૂલ્ય સોંપેલ શિરોબિંદુઓ 2D ટોપોલોજિકલ ગ્રીડમાં તેમના પડોશીઓ સાથે જોડાયેલા હોય છે, પરંતુ શિરોબિંદુઓને સોંપેલ અવકાશી કોઓર્ડિનેટ્સ 2D, 3D અથવા ઉચ્ચ પરિમાણોમાં હોઈ શકે છે. ઉદાહરણ તરીકે, ત્રિકોણાકાર જાળીદાર 3D જગ્યામાં જડિત 2D માહિતી સપાટીનું પ્રતિનિધિત્વ કરી શકે છે, જ્યાં શિરોબિંદુઓની અવકાશી સ્થિતિ અને સમોચ્ચ સાથેના અંતર્વેષ્ટિત બિંદુઓ બધામાં 3 કોઓર્ડિનેટ્સ હશે. નોંધ લો કે ચોરસનો કેસ ફરીથી અસ્પષ્ટ છે, કારણ કે 3-પરિમાણીય જગ્યામાં જડિત ચતુર્ભુજ આવશ્યકપણે સમતલીય નથી, તેથી 3D માં પટ્ટાવાળી સપાટીઓ દોરવા માટે ભૌમિતિક પ્રક્ષેપણ યોજનાની પસંદગી છે. કામગીરીની વિચારણાઓ અલ્ગોરિધમ શરમજનક રીતે સમાંતર છે, કારણ કે તમામ કોષો પર સ્વતંત્ર રીતે પ્રક્રિયા કરવામાં આવે છે. સમાંતર અલ્ગોરિધમ લખવું સરળ છે એમ ધારીને કેઃ વહેંચાયેલ વાંચન-માત્ર ઇનપુટ સ્કેલર ક્ષેત્ર. વહેંચાયેલ એપેન્ડ-માત્ર ભૂમિતિ આઉટપુટ સ્ટ્રીમ. માર્ચિંગ સ્ક્વેરનું નિષ્કપટ અમલીકરણ કે જે દરેક કોષને સ્વતંત્ર રીતે પ્રક્રિયા કરે છે તે દરેક રેખીય પ્રક્ષેપણ બે વાર (આઇસોલાઈન) અથવા ચાર વખત (આઇસોબેન્ડ) કરશે. તેવી જ રીતે, આઉટપુટમાં અસંબદ્ધ રેખાઓ (આઇસોલાઈન) માટે 2D શિરોબિંદુઓની 2 નકલો અથવા બહુકોણ (આઇસોબેન્ડ્સ) માટે 4 નકલો હશે. [એવી ધારણાઓ હેઠળ કેઃ ગ્રીડ મોટી છે, જેથી મોટાભાગના કોષો આંતરિક હોય; અને આઇસોબેન્ડ્સનો સંપૂર્ણ સંલગ્ન સમૂહ બનાવવામાં આવી રહ્યો છે.] ઇન્ટરપોલેશનના પરિણામોને કેશ કરીને કોમ્પ્યુટેશનલ ઓવરહેડને ઘટાડવું શક્ય છે. ઉદાહરણ તરીકે, સિંગલ-થ્રેડેડ સીરીયલ વર્ઝનને માત્ર ઇનપુટ ગ્રીડની એક પંક્તિ માટે ઇન્ટરપોલેટેડ પરિણામોને કેશ કરવાની જરૂર પડશે. અનુક્રમિત ભૌમિતિક આદિકાળનો ઉપયોગ કરીને ઉત્પાદનનું કદ ઘટાડવું પણ શક્ય છે, એટલે કે. 2D શિરોબિંદુઓની શ્રેણી બનાવો અને શ્રેણીમાં ટૂંકા પૂર્ણાંક ઓફસેટ સાથે રેખાઓ અથવા બહુકોણનો ઉલ્લેખ કરો. સંદર્ભો બાહ્ય કડીઓ માર્ચિંગ સ્ક્વેર મેટલેબ અલ્ગોરિધમ-ઓપન-સોર્સ માર્ચિંગ સ્ક્વેર અલ્ગોરિધમ સમજવા માટે સરળ. જાવામાં જાવા માર્ચિંગ સ્ક્વેર્સ કોડમાં અમલીકરણ. 2D ડેટા સેટ અને થ્રેશોલ્ડને જોતાં, સરળ પ્લોટિંગ માટે જનરલપાથ [] આપે છે. મીન્ડરિંગ ટ્રાયેન્ગલ સમજૂતી અને નમૂના પાયથોન અમલીકરણ. સી માં માર્ચિંગ સ્ક્વેર્સ કોડ-માર્ચિંગ સ્ક્વેર્સ માટે સિંગલ હેડર લાઇબ્રેરી જે સરળ રેન્ડરિંગ માટે ત્રિકોણ મેશ નિકાસ કરી શકે છે. કમ્પ્યુટર ગ્રાફિક્સ અલ્ગોરિધમ્સ