পয়েন্ট কোয়াডট্রি হল একটি বাইনারি ট্রির একটি অভিযোজন যা 2-মাত্রিক পয়েন্ট ডেটা উপস্থাপন করার জন্য প্রয়োগ করা হয়েছে। সমস্ত quadtrees এর বৈশিষ্ট্য পয়েন্ট quadtree দ্বারা ভাগ করা হয়.
এটি প্রায়শই 2-মাত্রিক, অর্ডারকৃত ডেটা পয়েন্টগুলির তুলনা করার ক্ষেত্রে খুব দক্ষ, সাধারণত O(log n) সময়ে কার্যকর করা হয়। পয়েন্ট quadtrees সম্পূর্ণতা জন্য মূল্যবান উল্লেখ করা হয়, কিন্তু k-d গাছ সাধারণ বাইনারি অনুসন্ধানের জন্য টুল হিসাবে তাদের ছাড়িয়ে যায়।
পয়েন্ট quadtrees নিম্নরূপ নির্মিত হয়.
সন্নিবেশ করার পরের পয়েন্টটি দেওয়া, আমরা যে কোষে এটি রয়েছে সেটি গণনা করি এবং এটিকে গাছে যুক্ত করি।
নতুন বিন্দুটি এমনভাবে যুক্ত করা হয়েছে যে যে কোষে এটি রয়েছে সেটি বিন্দুর মধ্য দিয়ে চলা উল্লম্ব এবং অনুভূমিক রেখা দ্বারা চতুর্ভুজে বিভক্ত। ফলস্বরূপ, কোষগুলি আয়তক্ষেত্রাকার তবে অগত্যা বর্গক্ষেত্র নয়৷
এই গাছগুলিতে, প্রতিটি নোড একটি ইনপুট পয়েন্ট নিয়ে গঠিত।
যেহেতু সমতলের বিভাজন পয়েন্ট-প্রবেশের ক্রম দ্বারা নির্ধারিত হয়, তাই গাছের উচ্চতা সংবেদনশীল এবং সন্নিবেশের আদেশের উপর নির্ভরশীল। একটি ভুল ক্রমে সন্নিবেশ করালে ইনপুট পয়েন্টের সংখ্যায় রৈখিক উচ্চতার একটি ট্রি হতে পারে (যে বিন্দুতে এটি একটি লিঙ্ক-তালিকা হয়ে যায়)।
যদি পয়েন্ট-সেটটি স্থির হয়, তাহলে ভারসাম্যপূর্ণ উচ্চতার একটি গাছ তৈরি করতে প্রাক-প্রক্রিয়াকরণ করা যেতে পারে।
একটি পয়েন্ট কোয়াডট্রির জন্য নোড গঠন
একটি পয়েন্ট কোয়াডট্রির একটি নোড একটি বাইনারি গাছের একটি নোডের সাথে একই, প্রধান পার্থক্য হল এটি দুটি ("বাম" এবং "ডান") এর পরিবর্তে চারটি পয়েন্টার (প্রতিটি পয়েন্টার প্রতিটি কোয়াড্রেন্টের জন্য ব্যবহৃত হয়) এর সাথে যুক্ত। একটি সাধারণ বাইনারি গাছে। এছাড়াও একটি কী সাধারণত দুটি অংশে বিভক্ত হয়, x এবং y স্থানাঙ্ক উল্লেখ করে।
অতএব, একটি নোড নিম্নলিখিত তথ্য নিয়ে গঠিত
- চারটি পয়েন্টার:এগুলো হল কোয়াড[‘NW’], কোয়াড[‘NE’], কোয়াড[‘SW’], এবং কোয়াড[‘SE’]
- NW-North West, NE-North East, SW-South West, SE-South East
- বিন্দু; যার মধ্যে রয়েছে
- কী; সাধারণত x, y স্থানাঙ্ক হিসাবে চিহ্নিত করা হয়
- মান; যেমন একটি নাম
