কম্পিউটার

ডেটা স্ট্রাকচারে অঞ্চল চতুর্ভুজ


অঞ্চল কোয়াডট্রি একটি নির্দিষ্ট উপ-অঞ্চলের সাথে সম্পর্কিত ডেটা নিয়ে গঠিত প্রতিটি লিফ নোডের সাথে অঞ্চলটিকে চারটি সমান চতুর্ভুজ, সাবকোয়াড্রেন্ট ইত্যাদিতে ভাগ করে দুটি মাত্রায় স্থানের একটি বিভাজন উপস্থাপন করতে উপযোগী। গাছের প্রতিটি নোড হয় ঠিক চারটি বাচ্চার সাথে যুক্ত বা কোন বাচ্চা নেই (একটি পাতার নোড)। চতুর্গাছের উচ্চতা যেগুলি এই পচন কৌশল অনুসরণ করে (অর্থাৎ সাবকোয়াড্রেন্টগুলিকে উপ-বিভাজন করা যতক্ষণ না সাবকোয়াড্রেন্টে আকর্ষণীয় তথ্য না থাকে যার জন্য আরও পরিমার্জন প্রয়োজন) সংবেদনশীল এবং ভাঙ্গা স্থানের আকর্ষণীয় এলাকার স্থানিক বন্টনের উপর নির্ভরশীল। অঞ্চল কোয়াডট্রিকে এক প্রকার ট্রাই হিসাবে চিহ্নিত করা হয়।

n এর গভীরতা সহ একটি অঞ্চল কোয়াডট্রি 2n × 2n পিক্সেল সমন্বিত একটি চিত্র উপস্থাপনের জন্য প্রয়োগ করা যেতে পারে, যেখানে প্রতিটি পিক্সেলের মান হয় 0 বা 1। সমগ্র চিত্র অঞ্চলকে উপস্থাপন করতে রুট নোডটি কার্যকর। যদি কোনো অঞ্চলের পিক্সেল সম্পূর্ণরূপে 0s বা 1s না হয় তবে এটি উপবিভক্ত হয়। এই অ্যাপ্লিকেশানে, প্রতিটি লিফ নোড পিক্সেলের একটি ব্লক উপস্থাপন করতে উপযোগী যা হয় সমস্ত 0s বা সমস্ত 1s। স্থানের পরিপ্রেক্ষিতে সম্ভাব্য সঞ্চয় নোট করুন যখন এই গাছগুলি চিত্র সংরক্ষণের জন্য প্রয়োগ করা হয়; এই চিত্রগুলিতে প্রায়শই যথেষ্ট আকারের অনেক অঞ্চল থাকে যেগুলির রঙের মান সর্বত্র একই থাকে। ছবিতে প্রতিটি পিক্সেলের একটি বড় 2-ডাইমেনশনাল অ্যারে সঞ্চয় করার পরিবর্তে, একটি কোয়াডট্রি একই তথ্য ক্যাপচার করতে সক্ষম হতে পারে পিক্সেল-রেজোলিউশন আকারের কোষগুলির চেয়ে বড় বিভাজন স্তরগুলি যা আমাদের অন্যথায় প্রয়োজন হবে। পিক্সেল এবং ছবির আকারগুলি গাছের রেজোলিউশন এবং সামগ্রিক আকারকে আবদ্ধ করতে সক্ষম৷

একটি অঞ্চল কোয়াডট্রি একটি ডেটা ক্ষেত্রের পরিবর্তনশীল রেজোলিউশন উপস্থাপনা হিসাবেও প্রয়োগ করা যেতে পারে। যেমন, একটি এলাকার তাপমাত্রা একটি চতুষ্পদ গাছ হিসাবে সংরক্ষণ করা যেতে পারে, প্রতিটি পাতার নোড এটি প্রতিনিধিত্ব করে এমন উপ-অঞ্চল জুড়ে গড় তাপমাত্রা সংরক্ষণ করে।

যদি একটি অঞ্চল কোয়াডট্রি বিন্দু ডেটার একটি সেট (যেমন শহরগুলির একটি সেটের অক্ষাংশ এবং দ্রাঘিমাংশ) প্রতিনিধিত্ব করার জন্য প্রয়োগ করা হয়, তবে প্রতিটি পাতায় সর্বাধিক একটি একক বিন্দু না থাকা পর্যন্ত অঞ্চলগুলিকে উপবিভক্ত করা হয়৷


  1. ডেটা স্ট্রাকচারে ইন্টারভাল ট্রিস

  2. ডেটা স্ট্রাকচারে B+ ট্রি কোয়েরি

  3. ডেটা স্ট্রাকচারে কম্প্রেসড কোয়াডট্রিস এবং অকট্রিস

  4. অর্ধেক ডাটা স্ট্রাকচার