पॉइंट क्वाडट्री (Point Quadtree) 2-आयामी पॉइंट डेटा को प्रस्तुत करने के लिए लागू बाइनरी ट्री (Binary Tree) का एक अनुकूलन (Adaptation) है। सभी क्वाडट्रीज़ की विशेषताएं पॉइंट क्वाडट्री द्वारा साझा की जाती हैं।
यह अक्सर 2-आयामी, क्रमबद्ध डेटा बिंदुओं की तुलना में बहुत कुशल होता है, आमतौर पर O(log n) समय में निष्पादित होता है। पॉइंट क्वाडट्रीज़ पूर्णता के लिए उल्लेखनीय हैं, लेकिन k-d ट्रीज़ सामान्यीकृत बाइनरी खोज के लिए उपकरण के रूप में उनसे बेहतर हैं।
पॉइंट क्वाडट्रीज़ निम्नानुसार बनाए जाते हैं।
अगले सम्मिलित किए जाने वाले बिंदु को देखते हुए, हम उस सेल की गणना करते हैं जिसमें यह स्थित है और इसे ट्री में जोड़ते हैं।
नया बिंदु इस तरह जोड़ा जाता है कि वह सेल जिसमें यह होता है, उस बिंदु से गुजरने वाली ऊर्ध्वाधर (Vertical) और क्षैतिज (Horizontal) रेखाओं द्वारा चतुर्थांशों में विभाजित हो जाता है। नतीजतन, सेल आयताकार (Rectangular) होते हैं लेकिन जरूरी नहीं कि वर्गाकार (Square) हों।
इन ट्रीज़ में, प्रत्येक नोड इनपुट बिंदुओं में से एक से बना होता है।
चूंकि प्लेन का विभाजन पॉइंट-इंसर्शन के क्रम द्वारा निर्धारित होता है, ट्री की ऊंचाई इंसर्शन ऑर्डर के प्रति संवेदनशील और निर्भर होती है। गलत क्रम में सम्मिलित करने से ट्री की ऊंचाई इनपुट बिंदुओं की संख्या में रैखिक हो सकती है (उस बिंदु पर यह एक लिंक्ड-लिस्ट बन जाती है)।
यदि पॉइंट-सेट स्टैटिक है, तो संतुलित ऊंचाई का ट्री बनाने के लिए प्री-प्रोसेसिंग की जा सकती है।
पॉइंट क्वाडट्री के लिए नोड संरचना (Node Structure for a Point Quadtree)
पॉइंट क्वाडट्री का एक नोड बाइनरी ट्री के नोड के समान होता है, जिसमें प्रमुख अंतर यह है कि यह चार पॉइंटर्स (प्रत्येक चतुर्थांश के लिए एक पॉइंटर) से जुड़ा होता है बजाय दो ("लेफ्ट" और "राइट") के जैसा कि एक सामान्य बाइनरी ट्री में होता है। साथ ही एक कुंजी (Key) को आमतौर पर दो भागों में विभाजित किया जाता है, जो x और y निर्देशांकों को संदर्भित करते हैं।
इसलिए, एक नोड में निम्नलिखित जानकारी होती है:
- चार पॉइंटर्स: ये quad['NW'], quad['NE'], quad['SW'], और quad['SE'] हैं
- NW-नॉर्थ वेस्ट, NE-नॉर्थ ईस्ट, SW-साउथ वेस्ट, SE-साउथ ईस्ट
- पॉइंट; जो बदले में निम्न से बना होता है
- कुंजी; आमतौर पर x, y निर्देशांक के रूप में दर्शाया जाता है
- मान; जैसे एक नाम
