एक सप्तक वृक्ष एक वृक्ष जैसी डेटा संरचना है, जिसके प्रत्येक नोड में आठ वंशज हैं। ऑक्टो-ट्री का उपयोग स्थानिक अनुक्रमण, त्रि-आयामी अंतरिक्ष में टकराव का पता लगाने, छिपी सतहों के निर्धारण, किरण अनुरेखण और परिमित तत्व विधि के लिए किया जाता है।
ऑक्ट्री को एक पदानुक्रमित डेटा संरचना या रैखिक रूप से दर्शाया जा सकता है।
पदानुक्रमित डेटा संरचना में एक पेड़ की जड़, नोड्स और पत्तियां होती हैं। प्रत्येक नोड अपने वंशजों को इंगित करता है।
एक रैखिक प्रतिनिधित्व के साथ, पॉइंटर्स का उपयोग नहीं किया जाता है - कोडिंग तत्वों के विभिन्न तरीकों का उपयोग किया जाता है और केवल पेड़ की पत्तियों को संग्रहीत किया जाता है।
सबसे आम और प्रभावी कोडिंग विधियों में से एक है लेबेसेग वक्र (जेड-वक्र) और हिल्बर्ट वक्र का उपयोग।
हिल्बर्ट वक्र का लाभ इसकी निरंतरता है - पड़ोसी तत्वों को श्रृंखला में व्यवस्थित किया जाता है। जेड-वक्र का लाभ इसकी सादगी और गणना की गति है, इसलिए इसे अक्सर अभ्यास में उपयोग किया जाता है।
दो आयामी Lebesgue वक्र
तीन आयामी Lebesgue वक्र
हिल्बर्ट द्वि-आयामी वक्र
हिल्बर्ट त्रि-आयामी वक्र
जेड-वक्र का उपयोग करने वाले तत्वों को एनकोड करने के लिए, मॉर्टन कोड का उपयोग किया जाता है (आमतौर पर कोड की गणना न्यूनतम निर्देशांक वाले नोड के लिए की जाती है)। जेड-वक्र के लिए मॉर्टन कोड की गणना प्रत्येक समन्वय के द्विआधारी प्रतिनिधित्व के बिट्स को स्थानांतरित करने और मिश्रण द्वारा की जाती है।
मॉर्टन कोड गणना उदाहरण
जेड-वक्र के गुणों को देखते हुए, तत्वों के लिए केवल तत्व की गहराई (ओक्ट्री ट्री में स्तर) और इसके क्रम (जेड-वक्र पर स्थान) को संग्रहीत करना आवश्यक है। तत्व की गहराई के मानों का उपयोग ग्रिड कोशिकाओं के भंडारण के लिए उपयोग किए गए सरणी के तत्वों में किया जाता है, और तत्व सूचकांक जेड-वक्र पर अपना स्थान निर्धारित करता है।
किसी तत्व की गहराई को संग्रहीत करने के लिए, यह 1 बाइट (पेड़ की गहराई 256) का उपयोग करने के लिए पर्याप्त है। कई कार्यों के लिए, 16 की एक पेड़ की गहराई पर्याप्त हो सकती है (न्यूनतम सेल का आकार मूल क्षेत्र की तुलना में 2 ^ 15 = 32768 गुना छोटा होगा)। फिर एक सेल के भंडारण के लिए 4 बिट का उपयोग करने के लिए पर्याप्त है।
किसी तत्व के वास्तविक निर्देशांक को निर्धारित करने के लिए, आपको निम्नलिखित चरण करने होंगे:
1. एक तत्व के लिए मॉर्टन कोड की गणना
2. डिकोडिंग
3. प्रत्येक निर्देशांक के वास्तविक मूल्य में परिणामी सूचकांक का अनुवाद
20 बिट्स के साथ प्रत्येक समन्वय को एन्कोडिंग के उदाहरण का उपयोग करके एल्गोरिथ्म पर विचार करें, अर्थात्, सभी तीन निर्देशांक के परिणामस्वरूप कोड 60 बिट्स पर कब्जा कर लेगा।
पिछले तत्व के कोड और गहराई को जानने के बाद, आप वर्तमान तत्व के कोड की गणना कर सकते हैं। पहले तत्व का कोड हमेशा 0 होता है। प्रत्येक गहराई स्तर के लिए ऑफसेट का निर्धारण करें:
for ( unsigned char i = 0; i < 21; ++i ) { levelOffset[20 - i] = offset; offset *= 8; }
अब हम पिछले तत्व की गहराई और सूचकांक के माध्यम से तत्व के सूचकांक का निर्धारण करेंगे:
unsigned long getElementIndex( const unsigned long prevIndex, const unsigned char prevLevel ) { return prevIndex + levelOffset[prevLevel]; }
डिकोडिंग समारोह:
void decodeIndexXYZ( const unsigned long index, unsigned long iXYZ[3]) { iXYZ[0] = decodeIndex( index ); iXYZ[1] = decodeIndex( index >> 1 ); iXYZ[2] = decodeIndex( index >> 2 ); } unsigned long decodeIndex( const unsigned long index ) { unsigned long ind = index & 0x0249249249249249; ind = ( ind | ( ind >> 2 ) ) & 0x00C9219243248649; ind = ( ind | ( ind >> 2 ) ) & 0x00386070C0E181C3; ind = ( ind | ( ind >> 4 ) ) & 0x0003E007C00F801F; ind = ( ind | ( ind >> 10 ) ) & 0x000000FFC00003FF; ind = ( ind | ( ind >> 20 ) ) & 0x00000000000FFFFF; return ind; }
iXYZ [0], iXYZ [1], iXYZ [2] - एन्कोडिंग क्रम निर्धारित करें (इस मामले में, पहले x समन्वय करें, फिर y, फिर z)।
डिकोडइंडेक्स फ़ंक्शन में स्थिरांक और चरणों की संख्या बिट्स की संख्या और अंतरिक्ष के आयाम से निर्धारित होती है (इस उदाहरण में, स्थिरांक तीन-आयामी स्थान और प्रति समन्वय 20 बिट्स के लिए दिए गए हैं)।
विभिन्न कोडिंग विधियां हैं, उदाहरण पर
बिट ट्विगलिंग हैक्सएक 3 डी मोर्टन संख्या की गणना कैसे करें (3 इंच के बिट्स को इंटरलेव करें)न्यूनतम निर्देशांक के साथ सेल वर्टेक्स के वास्तविक मूल्यों को प्राप्त करने के लिए, परिणामस्वरूप सूचकांकों को चरण आकार से गुणा किया जाता है। चरण का आकार न्यूनतम स्वीकार्य ग्रिड सेल का आकार है।
कोशिका का आकार इसकी गहराई से निर्धारित किया जा सकता है। शेष मूल्यों को तत्वों के आकार को संबंधित न्यूनतम निर्देशांक में जोड़कर निर्धारित किया जाता है।
तत्व का विभाजन उसकी गहराई को बढ़ाकर और उसके बाद उसी गहराई के 7 तत्वों को सम्मिलित करके किया जाता है।
मर्ज - गहराई कम करें और अगले 7 तत्वों को हटा दें।
ओक्टोडेरेवो एक सक्रिय रूप से अध्ययन की गई डेटा संरचना है और इसके साथ काम करने के लिए एल्गोरिदम (पड़ोसियों की खोज, अंतराल, दृश्य आदि) डॉक्टरेट शोध प्रबंध और वैज्ञानिक अनुसंधान का विषय बन जाते हैं।