কোয়াডট্রি হলো ট্রি যেগুলো দক্ষতার সাথে স্টোর করে পয়েন্টের ডেটা একটি টু-ডাইমেনশনাল স্পেসে। এই ট্রিতে, প্রতিটি নোডের সর্বোচ্চ চারটি চাইল্ড থাকে।
আমরা একটি কোয়াডট্রি বিল্ড করতে পারি একটি টু-ডাইমেনশনাল এরিয়া থেকে নিচের স্টেপগুলো ফলো করে:
- কারেন্ট টু-ডাইমেনশনাল স্পেস চারটি বক্সে ভাগ করা হয়।
- যদি একটি বক্স এক বা অধিক পয়েন্ট কন্টেইন করে, একটি চাইল্ড অবজেক্ট তৈরি করা হয়, সেটি স্টোর করে বক্সের টু-ডাইমেনশনাল স্পেস।
- যদি একটি বক্স কোনো পয়েন্ট কন্টেইন না করে, সেটির জন্য কোনো চাইল্ড তৈরি করা হয় না।
- প্রতিটি চাইল্ডের জন্য রিকার্শন করা হয়।
কোয়াডট্রি ব্যবহার করা হয় ইমেজ কমপ্রেশনে, যেখানে প্রতিটি নোড এর চাইল্ডদের এভারেজ কালার নিয়ে গঠিত।
ট্রিতে যত গভীর যাব, তত ইমেজের ডিটেইল।
কোয়াডট্রি ব্যবহার করা হয় টু-ডাইমেনশনাল এরিয়ায় নোড সার্চ করার জন্যও। উদাহরণস্বরূপ, যদি আমরা দিতে চাই দেওয়া কোঅর্ডিনেটের নিকটতম পয়েন্ট, আমরা কোয়াডট্রি ব্যবহার করে করতে পারি।
ইনসার্ট ফাংশন (Insert Function)
ইনসার্ট ফাংশন ব্যবহার করা হয় একটি নোড ইনসার্ট করতে একটি এক্সিস্টিং কোয়াড ট্রিতে। এই ফাংশন প্রথমে যাচাই করে দেওয়া নোড করেন্ট কোয়াডের বাউন্ডেরি درونেই আছে কিনা। যদি না হয়, তবে আমরা তৎক্ষণ ইনসার্শন ক্যাঞ্সেল করি। যদি বাউন্ডেরি درونেই থাকে, তবে উপযুক্ত চাইল্ড সিলেক্ট করা হয় এই নোড কন্টেইন করতে এর লোকেশন বেসড ওপর। এই ফাংশন O(Log N) যেখানে N ডিস্ট্যান্সের সাইজ নির্দেশ করে।
সার্চ ফাংশন (Search Function)
সার্চ ফাংশন ব্যবহার করা হয় একটি নোড লোকেট করতে দেওয়া কোয়াডে। এটি এডিট করা যেতে পারে নিকটতম নোড রিটার্ন করতে দেওয়া পয়েন্টের। এই ফাংশন অ্যাপ্লাই করা হয় দেওয়া পয়েন্ট নেওয়া, চাইল্ড কোয়াডের বাউন্ডেরির সাথে কমপেয়ার করে এবং রিকার্সিং। এই ফাংশন O(Log N) যেখানে N ডিস্ট্যান্সের সাইজ নির্দেশ করে।
কোয়াডট্রির কিছু সাধারণ ব্যবহার
- ইমেজ রিপ্রেজেন্টেশন
- ইমেজ প্রসেসিং
- মেশ জেনারেশন
- দুই ডাইমেনশনে ইফিশিয়েন্ট কলিশন ডিটেকশন
- বহুমাত্রিক ফিল্ডের সমাধান (কম্পিউটেশনাল ফ্লুইড ডাইনামিক্স, ইলেক্ট্রোম্যাগনেটিজম)
- স্টেট এস্টিমেশন
- ফ্র্যাক্টাল ইমেজ অ্যানালিসিস-এ কোয়াডট্রি ব্যবহার করা হয়
