পয়েন্ট কোয়াডট্রি হলো একটি বাইনারি ট্রির অ্যাডাপ্টেশন ২-ডাইমেনশনাল পয়েন্ট ডেটা রিপ্রেজেন্ট করতে। সকল কোয়াডট্রির ফিচার শেয়ার করা হয় পয়েন্ট কোয়াডট্রি দিয়ে।
এটি প্রায়ই খুব ইফিশিয়েন্ট ২-ডাইমেনশনাল, অর্ডারড ডেটা পয়েন্ট কমপেয়ার করতে, সাধারণত O(log n) টাইমে এক্সিকিউট করে। পয়েন্ট কোয়াডট্রি কোম্প্লিটনেসের জন্য ভ্যালুয়েবল মেনশন করা হয়, কিন্তু k-d ট্রি সেগুলোকে ছাড়িয়ে যায় জেনারেলাইজড বাইনারি সার্চের টুল হিসেবে।
পয়েন্ট কোয়াডট্রি নিম্নলিখিতভাবে বিল্ট হয়।
দেওয়া পয়েন্ট যেটি ইনসার্ট করা হবে, আমরা সেল ক্যালকুলেট করি যাতে সেটি লাই এবং ট্রিতে অ্যাড করি।
নতুন পয়েন্ট এভাবে অ্যাড করা হয় যাতে সেল যেটি সেটি কন্টেইন করে সেটি চতুর্ভাগে ভাগ হয় ভের্টিক্যাল এবং হরিজন্টাল লাইন দ্বারা যেগুলো পয়েন্টের মধ্য দিয়ে যায়। ফলস্বরূপ, সেলগুলো রেক্ট্যাঙ্গুলার কিন্তু অবশ্যই স্কোয়ার নয়।
এই ট্রিগুলোতে, প্রতিটি নোড ইনপুট পয়েন্টের একটিতে থাকে।
যেহেতু প্লেনের ডিভিশন নির্ভর করে পয়েন্ট-ইনসার্শন অর্ডারের ওপর, ট্রির হাইট সেন্সিটিভ এবং ডিপেন্ডেন্ট ইনসার্শন অর্ডারের ওপর। ভুল অর্ডারে ইনসার্ট করলে ট্রির হাইট লিনিয়ার হয়ে যাবে ইনপুট পয়েন্টের সংখ্যার সাথে (যে পয়েন্টে এটি একটি লিংকড-লিস্ট হয়ে যায়)।
যদি পয়েন্ট-সেট স্ট্যাটিক হয়, প্রি-প্রসেসিং করা যায় একটি ব্যালেন্সড হাইটের ট্রি বিল্ড করতে।
পয়েন্ট কোয়াডট্রির জন্য নোড স্ট্রাকচার
একটি পয়েন্ট কোয়াডট্রির নোড সমান একটি বাইনারি ট্রির নোড, প্রধান পার্থক্য হলো এটি চারটি পয়েন্টার সাথে অ্যাসোসিয়েটেড (প্রতিটি পয়েন্টার প্রতিটি কোড্রেন্টের জন্য) বদলে দুইটি ("left" এবং "right") একটি সাধারণ বাইনারি ট্রির মতো। এছাড়া একটি কী সাধারণত দুটি অংশে ভাঙা হয়, x এবং y কোঅর্ডিনেট রেফার করে।
অতএব, একটি নোড নিচের ইনফরমেশন নিয়ে গঠিত:
- চারটি পয়েন্টার: এগুলো হলো quad['NW'], quad['NE'], quad['SW'], এবং quad['SE']
- NW-নর্থ ওয়েস্ট, NE-নর্থ ইস্ট, SW-সাউথ ওয়েস্ট, SE-সাউথ ইস্ট
- পয়েন্ট; যা যেটা গঠিত:
- কী; সাধারণত x, y কোঅর্ডিনেট হিসেবে ডেনোট করা হয়
- ভ্যালু; যেমন একটি নাম
