Marching squares
কম্পিউটার গ্রাফিক্সে, মার্চিং স্কোয়ার হল একটি অ্যালগরিদম যা একটি দ্বি-মাত্রিক স্কেলার ক্ষেত্রের (পৃথক সংখ্যাসূচক মানগুলির আয়তক্ষেত্রাকার অ্যারে) জন্য কনট্যুর তৈরি করে। 2ডি ত্রিভুজ জালের কনট্যুর করার জন্য একটি অনুরূপ পদ্ধতি ব্যবহার করা যেতে পারে। কনট্যুরগুলি দুই ধরনের হতে পারেঃ আইসোলাইন-একটি একক তথ্য স্তর অনুসরণকারী লাইন, অথবা আইসোভ্যালু। আইসোব্যান্ড-আইসোলাইনের মধ্যে ভরা এলাকা। সাধারণ প্রয়োগগুলির মধ্যে রয়েছে টপোগ্রাফিক মানচিত্রে কনট্যুর লাইন বা আবহাওয়ার মানচিত্রের জন্য আইসোবার তৈরি করা। মার্চিং স্কোয়ারগুলি থ্রিডি মার্চিং কিউব অ্যালগরিদমের অনুরূপ পদ্ধতি গ্রহণ করেঃ গ্রিডের প্রতিটি কোষকে স্বাধীনভাবে প্রক্রিয়া করুন। কোষের কোণে ডেটা মানের সাথে কনট্যুর স্তরের (গুলি) তুলনা ব্যবহার করে একটি কোষ সূচক গণনা করুন। কোষের আউটপুট জ্যামিতি বর্ণনা করতে কোষ সূচকে কী করা একটি প্রাক-নির্মিত লুকআপ টেবিল ব্যবহার করুন। সঠিক কনট্যুর অবস্থান গণনা করতে কোষের সীমানা বরাবর রৈখিক ইন্টারপোলেশন প্রয়োগ করুন। মৌলিক অ্যালগরিদম এখানে অ্যালগরিদমের ধাপগুলি রয়েছেঃ একটি বাইনারি চিত্র তৈরি করতে 2ডি ক্ষেত্রে একটি সীমা প্রয়োগ করুনঃ 1 যেখানে ডেটা মান আইসোভ্যালু 0-এর উপরে যেখানে ডেটা মান আইসোভ্যালু-এর নীচে থাকে বাইনারি চিত্রের পিক্সেলের প্রতিটি 2x2 ব্লক একটি কনট্যুরিং সেল গঠন করে, তাই পুরো চিত্রটি এই ধরনের কোষের একটি গ্রিড দ্বারা প্রতিনিধিত্ব করা হয় (নীচের ছবিতে সবুজ রঙে দেখানো হয়েছে)। মনে রাখবেন যে এই কনট্যুরিং গ্রিডটি মূল 2ডি ক্ষেত্রের তুলনায় প্রতিটি দিকে একটি করে সেল ছোট। কনট্যুরিং গ্রিডের প্রতিটি কোষের জন্যঃ একটি বাইনারি সূচক তৈরি করতে কোষের কোণে 4টি বিট তৈরি করুনঃ সূচকের সাথে বিট যুক্ত করে ঘড়ির কাঁটার দিকে কোষের চারপাশে হাঁটুন, বিটওয়াইজ ওআর এবং বাম-শিফট ব্যবহার করে, উপরের বাম দিকের সবচেয়ে উল্লেখযোগ্য বিট থেকে, নীচে বাম দিকে কমপক্ষে উল্লেখযোগ্য বিট পর্যন্ত। ফলস্বরূপ 4-বিট সূচকের 0-15 পরিসরে 16টি সম্ভাব্য মান থাকতে পারে। সেলের প্রতিনিধিত্ব করার জন্য প্রয়োজনীয় প্রান্তগুলি তালিকাভুক্ত করে 16টি এন্ট্রি সহ একটি প্রাক-নির্মিত লুকআপ টেবিল অ্যাক্সেস করতে সেল সূচকটি ব্যবহার করুন (নীচের ছবির নীচের ডান অংশে দেখানো হয়েছে)। কোষের প্রান্ত বরাবর কনট্যুর লাইনের সঠিক অবস্থান খুঁজে পেতে মূল ক্ষেত্রের ডেটা মানগুলির মধ্যে রৈখিক ইন্টারপোলেশন প্রয়োগ করুন। স্যাডল পয়েন্টগুলির দ্ব্যর্থতা নিরসন স্যাডল পয়েন্টগুলিতে কনট্যুর দ্ব্যর্থহীন। ইন্টারপোলেটেড পয়েন্টগুলির বিভিন্ন সংযোগের মধ্যে বেছে নেওয়ার জন্য কোষের কেন্দ্রের গড় ডেটা মান ব্যবহার করে অস্পষ্টতা সমাধান করা সম্ভব (নীচে-ডান কোণে চারটি চিত্র): আইসোব্যান্ডস উপরের এবং নীচের প্রান্তিক মানগুলির মধ্যে ভরাট কনট্যুর ব্যান্ডগুলির জন্য অনুরূপ অ্যালগরিদম তৈরি করা যেতে পারেঃ কনট্যুরিং ত্রিভুজ জাল একই মৌলিক অ্যালগরিদম ত্রিভুজাকার জালগুলিতে প্রয়োগ করা যেতে পারে, যা শীর্ষে নির্ধারিত ডেটা সহ সংযুক্ত ত্রিভুজ নিয়ে গঠিত। উদাহরণস্বরূপ, ডেটা ক্ষেত্রটিকে কনট্যুর করার অনুমতি দেওয়ার জন্য ডেটা পয়েন্টগুলির একটি ছড়িয়ে ছিটিয়ে থাকা সেটকে ডেলাউনে ত্রিভুজের সাথে সংযুক্ত করা যেতে পারে। একটি ত্রিভুজাকার কোষ সর্বদা সমতলীয় হয়, কারণ এটি একটি 2-সরল (অর্থাৎ। একটি এন-মাত্রিক স্থানে এন + 1 শীর্ষ দ্বারা নির্দিষ্ট)। একটি ত্রিভুজ জুড়ে সর্বদা একটি অনন্য রৈখিক অন্তর্বর্তী থাকে এবং একটি দ্ব্যর্থহীন স্যাডলের কোনও সম্ভাবনা থাকে না। আইসোলাইন ত্রিভুজের উপর আইসোলাইনের বিশ্লেষণ বিশেষভাবে সহজঃ 3টি বাইনারি সংখ্যা রয়েছে, তাই 8টি সম্ভাবনা রয়েছেঃ আইসোব্যান্ড ত্রিভুজগুলির উপর আইসোব্যান্ডগুলির বিশ্লেষণের জন্য 3টি ত্রয়ী ট্রিট প্রয়োজন, তাই 27টি সম্ভাবনা রয়েছেঃ মাত্রা এবং স্থান মার্চিং স্কোয়ার অ্যালগরিদমের জন্য ডেটা স্পেস 2ডি, কারণ একটি ডেটা মান নির্ধারিত শীর্ষগুলি 2ডি টপোলজিকাল গ্রিডে তাদের প্রতিবেশীদের সাথে সংযুক্ত থাকে, তবে শীর্ষে নির্ধারিত স্থানিক স্থানাঙ্কগুলি 2ডি, 3ডি বা উচ্চতর মাত্রায় হতে পারে। উদাহরণস্বরূপ, একটি ত্রিভুজাকার জাল 3ডি স্পেসে এম্বেড করা একটি 2ডি ডেটা পৃষ্ঠের প্রতিনিধিত্ব করতে পারে, যেখানে একটি কনট্যুর বরাবর শীর্ষ এবং ইন্টারপোলেটেড পয়েন্টগুলির স্থানিক অবস্থানগুলির 3টি স্থানাঙ্ক থাকবে। লক্ষ্য করুন যে বর্গক্ষেত্রের বিষয়টি আবার দ্ব্যর্থহীন, কারণ ত্রিমাত্রিক স্থানে এম্বেড করা একটি চতুর্ভুজ অগত্যা সমতলীয় নয়, তাই 3D-তে ব্যান্ডযুক্ত পৃষ্ঠগুলি আঁকার জন্য জ্যামিতিক ইন্টারপোলেশন স্কিমের একটি পছন্দ রয়েছে। কর্মক্ষমতার বিবেচনা অ্যালগরিদমটি বিব্রতকরভাবে সমান্তরাল, কারণ সমস্ত কোষ স্বাধীনভাবে প্রক্রিয়া করা হয়। একটি সমান্তরাল অ্যালগরিদম লেখা সহজ এই ধরে নিয়ে যেঃ শেয়ারড রিড-অনলি ইনপুট স্কেলার ফিল্ড। শেয়ারড অ্যাপেন্ড-অনলি জ্যামিতি আউটপুট স্ট্রিম। মার্চিং স্কোয়ারের একটি সরল বাস্তবায়ন যা প্রতিটি কোষকে স্বাধীনভাবে প্রক্রিয়া করে প্রতিটি রৈখিক ইন্টারপোলেশন দুইবার (আইসোলাইন) বা চারবার (আইসোব্যান্ড) সম্পাদন করবে। একইভাবে, আউটপুটটিতে বিচ্ছিন্ন রেখার (আইসোলাইন) জন্য 2ডি শীর্ষের 2টি কপি বা বহুভুজের (আইসোব্যান্ড) জন্য 4টি কপি থাকবে। [এই অনুমানের অধীনে যেঃ গ্রিডটি বড়, যাতে বেশিরভাগ কোষ অভ্যন্তরীণ হয়; এবং আইসোব্যান্ডগুলির একটি সম্পূর্ণ সংলগ্ন সেট তৈরি করা হচ্ছে।] ইন্টারপোলেশনের ফলাফলগুলি ক্যাশে করে গণনামূলক ওভারহেড হ্রাস করা সম্ভব। উদাহরণস্বরূপ, একটি একক-থ্রেডেড সিরিয়াল সংস্করণ শুধুমাত্র ইনপুট গ্রিডের একটি সারির জন্য ইন্টারপোলেটেড ফলাফল ক্যাশে করতে হবে। সূচকযুক্ত জ্যামিতিক আদিম ব্যবহার করে আউটপুটের আকার হ্রাস করাও সম্ভব, অর্থাৎ। 2ডি শীর্ষগুলির একটি অ্যারে তৈরি করুন এবং অ্যারেতে সংক্ষিপ্ত পূর্ণসংখ্যা অফসেট সহ লাইন বা বহুভুজ নির্দিষ্ট করুন। রেফারেন্স বাহ্যিক লিঙ্ক মার্চিং স্কোয়ার ম্যাটল্যাব অ্যালগরিদম-ওপেন-সোর্স মার্চিং স্কোয়ার অ্যালগরিদম বোঝা সহজ। জাভাতে জাভা মার্চিং স্কোয়ার কোডে বাস্তবায়ন। একটি 2ডি ডেটা সেট এবং থ্রেশহোল্ড দেওয়া হলে, সহজ প্লটিংয়ের জন্য জেনারেলপাথ [] প্রদান করে। তির্যক ত্রিভুজ ব্যাখ্যা এবং নমুনা পাইথন বাস্তবায়ন। সি-তে মার্চিং স্কোয়ার কোড-মার্চিং স্কোয়ারের জন্য একটি একক হেডার লাইব্রেরি যা সহজ রেন্ডারিংয়ের জন্য ত্রিভুজ জাল রপ্তানি করতে পারে। কম্পিউটার গ্রাফিক্স অ্যালগরিদম