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

কম্প্রেসড কোয়াডট্রি (Compressed Quadtrees)

প্রতিটি সাবডিভাইডেড সেলের জন্য একটি নোড স্টোর করার সময়, আমরা অনেক খালি নোড স্টোর করতে পারি। এমন স্পার্স ট্রির আকার কমাতে সম্ভব শুধু সাবট্রি স্টোর করে যাদের লিফে ইন্টারেস্টিং ডেটা থাকে (অর্থাৎ "ইম্পোর্ট্যান্ট সাবট্রি")। আবার আমরা আকার আরও কমাতে পারি। যখন আমরা শুধু ইম্পোর্ট্যান্ট সাবট্রি বিবেচনা করি, প্রুনিং প্রসেস লং পাথ এড়াতে পারে ট্রিতে যেখানে ইন্টারমিডিয়েট নোডের ডিগ্রি দুই (এক প্যারেন্ট এবং এক চাইল্ডের লিংক)। আউট কামস যে আমাদের শুধু নোড U স্টোর করতে হয় এই পাথের শুরুতে (এবং কিছু মেটা-ডেটা অ্যাসোসিয়েট করে ডিলিটেড নোড রিপ্রেজেন্ট করতে) এবং সাবট্রি আট্যাচ করা হয় U-র সাথে যেটি এর এন্ডে রুটেড। এই কম্প্রেসড ট্রিগুলো এখনও লিনিয়ার হাইট রাখে "খারাপ" ইনপুট পয়েন্টের দিয়ে।

যদিও আমরা ট্রির খুব বড় অংশ কাটায় দিয়ে এই কমপ্রেশন করি, এখনও লগারিদমিক-টাইম ইনসার্শন, ডিলিশন এবং সার্চ অর্জন করা সম্ভব Z-অর্ডার কার্ভের সুবিধা নেয়া। Z-অর্ডার কার্ভ প্রতিটি সেল অফ দ্য ফুল কোয়াডট্রি (অতএব কম্প্রেসড কোয়াডট্রি হলেও) O(1) টাইমে একটি ১-ডাইমেনশনাল লাইনে কনভার্ট করে (এবং O(1) টাইমে ফেরত আনে), এলিমেন্টগুলোর ওপর একটি টোটাল অর্ডার বিল্ড করে। এখন, আমরা কোয়াডট্রি স্টোর করতে পারি একটি অর্ডারড সেটের ডেটা স্ট্রাকচারে (যেখানে আমরা ট্রির নোডগুলো স্টোর করি)। এখন, আমাদের একটি রीজনেবল অনুমান করতে হবে এগিয়ে যাওয়ার আগে: আমরা অনুমান করি যে দুটি রিয়াল নাম্বার α,β € [0,1] বাইনারি হিসেবে দেওয়া হলে, আমরা O(1) টাইমে ক্যালকুলেট করতে পারি প্রথম বিটের ইনডেক্স যাতে তারা ভিন্ন। আমরা অনুমান করি যে আমরা O(1) টাইমে ক্যালকুলেট করতে পারি সবচেয়ে ছোট কমন 앙সেস্টর দুই পয়েন্ট/সেলের কোয়াডট্রি-এ এবং তাদের রিলেটিভ Z-অর্ডারিং স্থাপন করতে, এবং আমরা ফ্লোর ফাংশন O(1) টাইমে ক্যালকুলেট করতে পারি। এই অনুমানগুলোতে, পয়েন্ট লোকেশন একটি দেওয়া পয়েন্ট Q-এর জন্য (অর্থাৎ সেল খুঁজে বের করা যেটি Q কন্টেইন করবে), ডিলিশন এবং ইনসার্শন অপারেশন সব O(n log n) টাইমে করা যায় (অর্থাৎ টাইম লাগে অন্ডারলাইং অর্ডারড সেট ডেটা স্ট্রাকচারে সার্চ করতে)।

Q-র জন্য পয়েন্ট লোকেশন পারফর্ম করতে (অর্থাৎ কমপ্রেসড ট্রিতে এর সেল নির্ধারণ করা)

• কমপ্রেসড ট্রিতে এক্সিস্টিং সেল খুঁজে বের করা হয় যা Q-র আগে আসে Z-অর্ডারে। এই সেলকে V বলা হয়।
• যদি Q€V করা হয়, V রিটার্ন করা হয়।
• অন্যথায়, খুঁজে বের করা হয় কী হবে স্মলেস্ট কমন অ্যানসেস্টর পয়েন্ট Q এবং সেল V-র অনকমপ্রেসড কোয়াডট্রি-এ। এই অ্যানসেস্টর সেলকে U বলা হয়।
• কমপ্রেসড ট্রিতে এক্সিস্টিং সেল খুঁজে বের করা হয় যা U-র আগে আসে Z-অর্ডারে এবং সেটি রিটার্ন করা হয়।

স্পেসিফিক ডিটেইলস না জানাতে, ইনসার্শন এবং ডিলিশন পারফর্ম করতে আমরা প্রথমে পয়েন্ট লোকেশন পারফর্ম করি সেটির জন্য যা আমরা ইনসার্ট/ডিলিট করতে চাই, এবং তারপর ইনসার্ট/ডিলিট করি। কেয়ার নেওয়া হয় ট্রি রিশেপ করতে যথাযথভাবে, নোড তৈরি এবং ডিলিট করা প্রয়োজন অনুযায়ী।

অকট্রি (Octree)

একটি অকট্রি হলো একটি ট্রি ডেটা স্ট্রাকচার যেখানে প্রতিটি ইন্টারন্যাল নোড ঠিক আটটি চাইল্ডের সাথে অ্যাসোসিয়েটেড।

অকট্রি সবচেয়ে বেশি ব্যবহৃত হয় ৩-ডাইমেনশনাল স্পেস পার্টিশন করতে রিকার্সিভলি এটিকে আটটি অকটেন্টে সাবডিভাইড করে।

অকট্রি বিবেচিত হয় কোয়াডট্রির ৩-ডাইমেনশনাল аналগ। নাম তৈরি হয় oct + tree থেকে, কিন্তু লক্ষ্য করুন যে এটি সাধারণত "octree" লিখা হয় শুধু এক "t" দিয়ে।

অকট্রি প্রায়ই ব্যবহৃত হয় ৩ডি গ্রাফিক্স এবং ৩ডি গেম ইঞ্জিন-এ।

স্পেশিয়াল রিপ্রেজেন্টেশনের জন্য

অকট্রির প্রতিটি নোড দায়িত্বশীল স্পেস সাবডিভাইড করতে যা সেটি রিপ্রেজেন্ট করে আটটি অকটেন্টে। একটি পয়েন্ট রিজন (PR)

অকট্রিতে, নোড একটি এক্সপ্লিসিট ৩-ডাইমেনশনাল পয়েন্ট স্টোর করে, যা সেটি নোডের সাবডিভিশনের "সেন্টার"; পয়েন্টটি নির্দেশ করে আটটি চাইল্ডের যেকোনো একটি কোর্নার। একটি ম্যাট্রিক্স-বেসড (MX) অকট্রির ক্ষেত্রে, সাবডিভিশন পয়েন্ট ইমপ্লিসিটলি সেন্টার অফ দ্য স্পেস রিপ্রেজেন্টেড বাই দ্য নোড। PR অকট্রির রুট নোড ইনফিনিট স্পেস রিপ্রেজেন্ট করতে পারে; MX অকট্রির রুট নোড ফাইনাইট বাউন্ডেড স্পেস রিপ্রেজেন্ট করতে হবে যাতে ইমপ্লিসিট সেন্টারগুলো ভালোভাবে ডিফাইনড থাকে।

সাধারণ ব্যবহার

• ৩ডি কম্পিউটার গ্রাফিক্স-এ লেভেল অফ ডিটেইল রেন্ডারিং
• স্পেশিয়াল ইন্ডেক্সিং
• নیرেস্ট नेবর সার্চিং
• তিন ডাইমেনশনে ইফিশিয়েন্ট কলিশন ডিটেকশন
• ফাইনাইট এলিমেন্ট অ্যানালিসিস
• স্পার্স ভক্সেল অকট্রি
• স্টেট এস্টিমেশন
• সেট এস্টিমেশন