Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> प्रोग्रामिंग

डेटा स्ट्रक्चर में रीजन क्वाडट्रीज़

रीजन क्वाडट्री (Region Quadtree) दो आयामों में स्थान के विभाजन (Partition of Space) को प्रस्तुत करने के लिए उपयोगी है, क्षेत्र को चार बराबर चतुर्थांश (Quadrants), उप-चतुर्थांश (Subquadrants), और इसी तरह विभाजित करके, प्रत्येक लीफ नोड (Leaf Node) में एक विशिष्ट उपक्षेत्र (Subregion) से संबंधित डेटा होता है। ट्री में प्रत्येक नोड या तो ठीक चार बच्चों (Four Children) से जुड़ा होता है या कोई बच्चा नहीं (लीफ नोड)। क्वाडट्रीज़ की ऊंचाई जो इस विघटन रणनीति का पालन करती हैं (यानी उप-चतुर्थांशों को तब तक उप-विभाजित करना जब तक कि उस उप-चतुर्थांश के लिए दिलचस्प डेटा न हो जिसके लिए अधिक शोधन आवश्यक है) अंतरिक्ष में दिलचस्प क्षेत्रों के स्थानिक वितरण (Spatial Distribution) के प्रति संवेदनशील और निर्भर होती है जिसे विभाजित किया जा रहा है। रीजन क्वाडट्री को एक प्रकार का ट्राई (Trie) माना जाता है।

गहराई n का एक रीजन क्वाडट्री 2ⁿ × 2ⁿ पिक्सल्स से बनी छवि (Image) को प्रस्तुत करने के लिए लागू किया जा सकता है, जहां प्रत्येक पिक्सेल मान या तो 0 या 1 होता है। रूट नोड संपूर्ण छवि क्षेत्र को प्रस्तुत करने के लिए उपयोगी है। यदि किसी क्षेत्र के पिक्सेल न तो पूरी तरह 0 हैं और न ही 1, तो इसे उप-विभाजित किया जाता है। इस एप्लिकेशन में, प्रत्येक लीफ नोड पिक्सेल्स के एक ब्लॉक को प्रस्तुत करने के लिए उपयोगी है जो या तो सभी 0 हैं या सभी 1 हैं। जब इन ट्रीज़ को छवियों को स्टोर करने के लिए लागू किया जाता है तो स्पेस के मामले में संभावित बचत पर ध्यान दें; इन छवियों में अक्सर काफी बड़े क्षेत्र होते हैं जिनमें पूरी तरह से समान रंग मान होता है। छवि में हर पिक्सेल के एक बड़े 2-आयामी एरे को स्टोर करने के बजाय, एक क्वाडट्री संभावित रूप से कई विभाजन स्तरों तक बड़ी पिक्सेल-रिज़ॉल्यूशन आकार की सेल्स की तुलना में बड़ी सेल्स में वही जानकारी प्राप्त कर सकती है। पिक्सेल और छवि आकार ट्री रिज़ॉल्यूशन और समग्र आकार को बांधने में सक्षम हैं।

एक रीजन क्वाडट्री को डेटा फील्ड के परिवर्तनीय रिज़ॉल्यूशन प्रतिनिधित्व (Variable Resolution Representation) के रूप में भी लागू किया जा सकता है। जैसे, किसी क्षेत्र में तापमान को क्वाडट्री के रूप में संग्रहीत किया जा सकता है, प्रत्येक लीफ नोड उस उपक्षेत्र में औसत तापमान को संग्रहीत करता है जिसे वह दर्शाता है।

यदि एक रीजन क्वाडट्री का उपयोग पॉइंट डेटा के सेट को प्रस्तुत करने के लिए किया जाता है (जैसे शहरों के एक सेट की अक्षांश और देशांतर), तो क्षेत्रों को तब तक उप-विभाजित किया जाता है जब तक कि प्रत्येक लीफ में अधिकतम एक बिंदु न हो।

  1. डेटा संरचना में B+ ट्री क्वेरी (B+ tree Query) डेटा संरचना में B+ ट्री क्वेरी (B+ tree Query)

    यहाँ हम देखेंगे कि B+ ट्री में खोज कैसे की जाती है। B+ ट्री खोज को B+ ट्री क्वेरीिंग (B+ Tree Querying) के रूप में भी जाना जाता है। यह एल्गोरिदम B-ट्री की क्वेरी करने के समान है। इसके अलावा, यह रेंज क्वेरी (range query) का समर्थन करता है। मान लीजिए हमारे पास नीचे जैसा B+ ट्री है: B+ ट्री का उदाहरण

  1. डेटा स्ट्रक्चर में कंप्रेस्ड क्वाडट्रीज़ और ऑक्ट्रीज़ डेटा स्ट्रक्चर में कंप्रेस्ड क्वाडट्रीज़ और ऑक्ट्रीज़

    कंप्रेस्ड क्वाडट्रीज़ (Compressed Quadtrees) प्रत्येक उपविभाजित सेल (Subdivided Cell) से संबंधित नोड को स्टोर करते समय, हम बहुत सारे खाली नोड्स स्टोर कर सकते हैं। ऐसे विरल ट्रीज़ (Sparse Trees) के आकार को कम करना केवल उन सबट्रीज़ को स्टोर करके संभव है जिनके लीफ में दिलचस्प डेटा होता है (यानी महत्वपू

  1. हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure) हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure)

    परिचय (Introduction) टेम्पलेट पैरामीटर्स के लिए HDS या हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure - संक्षिप्त HalfedgeDS) को एक एज-केंद्रित डेटा स्ट्रक्चर (Edge-centered Data Structure) के रूप में परिभाषित किया जाता है जो वर्टेक्स, एज और फेसेस (Vertices, Edges and Faces) की घटना जानकारी (Incidenc