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

कंप्रेस्ड क्वाडट्रीज़ (Compressed Quadtrees)

प्रत्येक उपविभाजित सेल (Subdivided Cell) से संबंधित नोड को स्टोर करते समय, हम बहुत सारे खाली नोड्स स्टोर कर सकते हैं। ऐसे विरल ट्रीज़ (Sparse Trees) के आकार को कम करना केवल उन सबट्रीज़ को स्टोर करके संभव है जिनके लीफ में दिलचस्प डेटा होता है (यानी "महत्वपूर्ण सबट्रीज़")। फिर से हम आकार को और भी कम कर सकते हैं। जब हम केवल महत्वपूर्ण सबट्रीज़ पर विचार करते हैं, तो प्रूनिंग प्रक्रिया (Pruning Process) ट्री में उन लंबे पथों से बच सकती है जहां इंटरमीडिएट नोड्स की डिग्री दो होती है (एक पैरेंट और एक चाइल्ड का लिंक)। पता चलता है कि हमें केवल इस पथ की शुरुआत में नोड U को स्टोर करने की आवश्यकता है (और हटाए गए नोड्स का प्रतिनिधित्व करने के लिए इसके साथ कुछ मेटा-डेटा जोड़ें) और इसके अंत में रूटेड सबट्री को U से जोड़ें। ये कंप्रेस्ड ट्रीज़ "खराब" इनपुट पॉइंट्स दिए जाने पर अभी भी रैखिक ऊंचाई (Linear Height) रखते हैं।

हालांकि जब हम यह कम्प्रेशन करते हैं तो हम ट्री का बहुत सारा हिस्सा काट देते हैं, फिर भी Z-ऑर्डर कर्व्स (Z-order Curves) का लाभ उठाकर लॉगरिदमिक-समय सम्मिलन, विलोपन और खोज प्राप्त करना संभव है। Z-ऑर्डर कर्व फुल क्वाडट्री (और इसलिए कंप्रेस्ड क्वाडट्री भी) के प्रत्येक सेल को O(1) समय में 1-आयामी रेखा (1-Dimensional Line) में परिवर्तित करता है (और इसे O(1) समय में वापस भी परिवर्तित करता है), जिससे एलिमेंट्स पर एक टोटल ऑर्डर (Total Order) बनता है। अब, हम क्वाडट्री को ऑर्डर्ड सेट्स (Ordered Sets) के लिए एक डेटा स्ट्रक्चर में स्टोर कर सकते हैं (जिसमें हम ट्री के नोड्स को स्टोर करते हैं)। अब, जारी रखने से पहले एक उचित धारणा बतानी चाहिए: हम मान लेते हैं कि दो वास्तविक संख्याएं α, β ∈ [0,1] दिए जाने पर, बाइनरी में दर्शाए गए, हम O(1) समय में उस पहले बिट का इंडेक्स निकाल सकते हैं जिसमें वे भिन्न हैं। हम यह भी मानते हैं कि हम O(1) समय में क्वाडट्री में दो बिंदुओं/सेल्स के सबसे छोटे सामान्य पूर्वज (Lowest Common Ancestor) की गणना कर सकते हैं और उनके सापेक्ष Z-ऑर्डरिंग को स्थापित कर सकते हैं, और हम O(1) समय में फ्लोर फंक्शन की गणना कर सकते हैं। इन धारणाओं के साथ, दिए गए बिंदु Q का पॉइंट लोकेशन (यानी वह सेल ढूंढें जिसमें Q होगा), डिलीशन और इंसर्शन ऑपरेशन सभी O(n log n) समय में किए जा सकते हैं (यानी अंतर्निहित ऑर्डर्ड सेट डेटा स्ट्रक्चर में खोज करने में लगने वाला समय)।

Q के लिए पॉइंट लोकेशन करने के लिए (यानी कंप्रेस्ड ट्री में इसका सेल निर्धारित करना)

• कंप्रेस्ड ट्री में मौजूद सेल को ढूंढें जो Z-ऑर्डर में Q से पहले आता है। इस सेल को V कहें।
• यदि Q ∈ V है, तो V वापस करें।
• अन्यथा, एक अनकंप्रेस्ड क्वाडट्री में बिंदु Q और सेल V के सबसे छोटे सामान्य पूर्वज क्या होता, यह ढूंढें। इस पूर्वज सेल को U कहें।
• कंप्रेस्ड ट्री में मौजूद सेल को ढूंढें जो Z-ऑर्डर में U से पहले आता है और उसे वापस करें।

विशिष्ट विवरण में जाए बिना, इंसर्शन और डिलीशन करने के लिए हम पहले उस चीज़ के लिए पॉइंट लोकेशन करते हैं जिसे हम इंसर्ट/डिलीट करना चाहते हैं, और फिर उसे इंसर्ट/डिलीट करते हैं। ट्री को उचित रूप से रीशेप (Reshape) करने का ध्यान रखा जाना चाहिए, आवश्यकतानुसार नोड्स बनाना और हटाना।

ऑक्ट्री (Octree)

ऑक्ट्री को एक ट्री डेटा स्ट्रक्चर के रूप में परिभाषित किया जाता है जिसमें प्रत्येक आंतरिक नोड (Internal Node) ठीक आठ बच्चों (Eight Children) से जुड़ा होता है।

ऑक्ट्री का उपयोग अक्सर 3-आयामी स्थान को आठ ऑक्टेंट्स (Octants) में पुनरावर्ती रूप से उप-विभाजित करके पार्टीशन करने के लिए किया जाता है।

ऑक्ट्री को क्वाडट्रीज़ का 3-आयामी एनालॉग (3-Dimensional Analog) माना जाता है। नाम oct + tree से बना है, लेकिन ध्यान दें कि इसे आमतौर पर केवल एक "t" के साथ "octree" लिखा जाता है।

ऑक्ट्री का उपयोग अक्सर 3D ग्राफिक्स और 3D गेम इंजन में किया जाता है।

स्थानिक प्रतिनिधित्व के लिए

ऑक्ट्री में प्रत्येक नोड उस स्थान को आठ ऑक्टेंट्स में उप-विभाजित करने के लिए जिम्मेदार होता है जिसे वह दर्शाता है। पॉइंट रीजन (PR - Point Region) ऑक्ट्री में, नोड एक स्पष्ट 3-आयामी बिंदु स्टोर करता है, जो उस नोड के लिए उप-विभाजन का "केंद्र" होता है; वह बिंदु प्रत्येक आठ बच्चों के कोनों में से एक को निर्दिष्ट करता है। मैट्रिक्स-आधारित (MX - Matrix based) ऑक्ट्री के मामले में, उप-विभाजन बिंदु नोड द्वारा दर्शाए गए स्थान का केंद्र होता है। PR ऑक्ट्री का रूट नोड अनंत स्थान दर्शा सकता है; MX ऑक्ट्री का रूट नोड एक परिमित बाउंडेड स्थान दर्शाने में सक्षम होना चाहिए ताकि अंतर्निहित केंद्र अच्छी तरह से परिभाषित हों।

सामान्य उपयोग (Common Uses)

• 3D कंप्यूटर ग्राफिक्स में लेवल ऑफ डिटेल रेंडरिंग (Level of Detail Rendering)
• स्थानिक इंडेक्सिंग (Spatial Indexing)
• निकटतम पड़ोसी खोज (Searching Nearest Neighbour)
• तीन आयामों में कुशल टकराव पहचान (Efficient Collision Detection in Three Dimensions)
• फाइनाइट एलिमेंट विश्लेषण (Analysis of Finite Element)
• स्पार्स वॉक्सेल ऑक्ट्री (Sparse Voxel Octree)
• स्टेट एस्टीमेशन (Estimation of State)
• सेट एस्टीमेशन (Estimation of Set)