Quadtrees একটি দ্বি-মাত্রিক স্থানের পয়েন্টের ডেটা দক্ষতার সাথে সংরক্ষণ করার জন্য প্রয়োগ করা গাছ। এই গাছে, প্রতিটি নোডে সর্বাধিক চারটি শিশু রয়েছে৷
আমরা নিম্নলিখিত ধাপগুলি বাস্তবায়ন করে একটি দ্বি-মাত্রিক এলাকা থেকে একটি চতুষ্পদ গাছ তৈরি করতে পারি
- বর্তমান দ্বিমাত্রিক স্থান চারটি বাক্সে বিভক্ত।
- যদি একটি বাক্সে এক বা একাধিক বিন্দু থাকে, তাহলে একটি চাইল্ড অবজেক্ট তৈরি করুন, এতে বাক্সের দ্বিমাত্রিক স্থান সংরক্ষণ করুন।
- যদি একটি বাক্সে কোনো পয়েন্ট না থাকে, তাহলে এর জন্য একটি শিশু তৈরি করবেন না।
- প্রতিটি শিশুর জন্য পুনরাবৃত্তি সম্পাদন করুন।
Quadtrees ইমেজ কম্প্রেশনে প্রয়োগ করা হয়, যেখানে প্রতিটি নোডের প্রতিটি বাচ্চার গড় রঙ থাকে।
আমরা গাছের যত গভীরে যাই, চিত্রটির বিশদ তত বেশি।
Quadtrees একটি দ্বি-মাত্রিক এলাকায় নোড অনুসন্ধানে বাস্তবায়িত হয়. উদাহরণ স্বরূপ, আমরা যদি প্রদত্ত স্থানাঙ্কের নিকটতম বিন্দু গণনা করতে চাই, তাহলে আমরা এটি করতে পারি কোয়াডট্রিস প্রয়োগ করে।
ফাংশন সন্নিবেশ করান
একটি বিদ্যমান কোয়াড ট্রিতে একটি নোড সন্নিবেশ করার জন্য সন্নিবেশ ফাংশন প্রয়োগ করা হয়। এই ফাংশনটি প্রথমে যাচাই করে যে প্রদত্ত নোডটি বর্তমান কোয়াডের সীমানার মধ্যে আছে কিনা। যদি তা না হয়, তাহলে আমরা অবিলম্বে সন্নিবেশ বাতিল করি। যদি এটি সীমানার মধ্যে থাকে, তাহলে আমরা তার অবস্থানের উপর ভিত্তি করে এই নোডটি ধারণ করার জন্য উপযুক্ত শিশুটিকে বেছে নিই। এই ফাংশনটি হল O(লগ N) যেখানে N দূরত্বের আকার নির্দেশ করে।
অনুসন্ধান ফাংশন
প্রদত্ত কোয়াডে একটি নোড সনাক্ত করতে অনুসন্ধান ফাংশন প্রয়োগ করা হয়। প্রদত্ত বিন্দুতে নিকটতম নোডটি ফিরিয়ে দেওয়ার জন্যও এটি সম্পাদনা করা যেতে পারে। এই ফাংশনটি প্রদত্ত বিন্দু গ্রহণ করে, চাইল্ড কোয়াডের সীমানার সাথে তুলনা করে এবং পুনরাবৃত্তি করে প্রয়োগ করা হয়। এই ফাংশনটি হল O(লগ N) যেখানে N দূরত্বের আকার নির্দেশ করে।
quadtrees এর কিছু সাধারণ ব্যবহার
- চিত্রের চিত্র উপস্থাপনা
- চিত্রের চিত্র প্রক্রিয়াকরণ
- জালের জাল প্রজন্ম
- দুটি মাত্রায় দক্ষ সংঘর্ষ সনাক্তকরণ সম্পাদন করে
- বহুমাত্রিক ক্ষেত্রগুলির সমাধান খুঁজে বের করতে পারফর্ম করে (কম্পিউটেশনাল ফ্লুইড ডাইনামিকস, ইলেক্ট্রোম্যাগনেটিজম)
- রাষ্ট্রের অনুমান ফ্র্যাক্টাল ইমেজ অ্যানালাইসিসের ক্ষেত্রেও
- Quadtrees প্রয়োগ করা হয়
