क्वाडट्रीज़ (Quadtrees) दो-आयामी स्थान (Two-Dimensional Space) पर बिंदुओं के डेटा को कुशलतापूर्वक स्टोर करने के लिए लागू ट्रीज़ हैं। इस ट्री में, प्रत्येक नोड के अधिकतम चार बच्चे (Maximum Four Children) होते हैं।
हम निम्न चरणों को लागू करके दो-आयामी क्षेत्र से एक क्वाडट्री बना सकते हैं:
- वर्तमान दो-आयामी स्थान को चार बॉक्स (Boxes) में विभाजित किया जाता है।
- यदि एक बॉक्स में एक या अधिक बिंदु हैं, तो एक चाइल्ड ऑब्जेक्ट बनाएं, जिसमें बॉक्स का दो-आयामी स्थान स्टोर हो।
- यदि एक बॉक्स में कोई बिंदु नहीं है, तो उसके लिए चाइल्ड न बनाएं।
- प्रत्येक बच्चे के लिए पुनरावृत्ति (Recursion) करें।
क्वाडट्रीज़ का उपयोग छवि संपीड़न (Image Compression) में किया जाता है, जहां प्रत्येक नोड में उसके बच्चों में से प्रत्येक का औसत रंग (Average Colour) होता है।
हम ट्री में जितना गहरा जाते हैं, छवि का विवरण (Detail) उतना ही अधिक होता है।
क्वाडट्रीज़ का उपयोग दो-आयामी क्षेत्र में नोड्स की खोज के लिए भी किया जाता है। उदाहरण के लिए, यदि हम दिए गए निर्देशांकों के निकटतम बिंदु (Closest Point) की गणना करना चाहते हैं, तो हम इसे क्वाडट्रीज़ का उपयोग करके कर सकते हैं।
इन्सर्ट फंक्शन (Insert Function)
इन्सर्ट फंक्शन का उपयोग मौजूदा क्वाड ट्री में एक नोड सम्मिलित करने के लिए किया जाता है। यह फंक्शन पहले सत्यापित करता है कि दिया गया नोड वर्तमान क्वाड की सीमाओं (Boundaries) के भीतर है या नहीं। यदि नहीं है, तो हम तुरंत सम्मिलन रद्द कर देते हैं। यदि यह सीमाओं के भीतर है, तो हम इसकी लोकेशन के आधार पर इस नोड को समाहित करने के लिए उपयुक्त चाइल्ड चुनते हैं। यह फंक्शन O(log N) है जहां N दूरी के आकार (Size of Distance) को इंगित करता है।
सर्च फंक्शन (Search Function)
सर्च फंक्शन का उपयोग दिए गए क्वाड में एक नोड का पता लगाने के लिए किया जाता है। इसे दिए गए बिंदु के निकटतम नोड को वापस करने के लिए भी संपादित किया जा सकता है। यह फंक्शन दिए गए बिंदु को लेकर, चाइल्ड क्वाड्स की सीमाओं के साथ तुलना करके और पुनरावृत्ति करके लागू किया जाता है। यह फंक्शन O(log N) है जहां N दूरी के आकार को इंगित करता है।
क्वाडट्रीज़ के कुछ सामान्य उपयोग (Some Common Uses of Quadtrees)
- छवि का प्रतिनिधित्व (Image Representation)
- छवि प्रसंस्करण (Image Processing)
- मेश जनरेशन (Mesh Generation)
- दो आयामों में कुशल टकराव पहचान (Efficient Collision Detection in Two Dimensions)
- बहुआयामी क्षेत्रों का समाधान खोजना (Computational Fluid Dynamics, Electromagnetism)
- स्टेट एस्टीमेशन (Estimation of State)
- क्वाडट्रीज़ का उपयोग फ्रैक्टल छवि विश्लेषण (Fractal Image Analysis) के क्षेत्र में भी किया जाता है
