स्तर समुच्चय (डेटा संरचनाएं)

कंप्यूटर विज्ञान में एक स्तर सेट डेटा संरचना को अलग-अलग नमूनाकरण (सांख्यिकी) गतिशील स्तर सेट कार्यों का प्रतिनिधित्व करने के लिए डिज़ाइन किया गया है।

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

कालानुक्रमिक घटनाक्रम

शक्तिशाली स्तर-सेट विधि स्टेनली ओशर और जेम्स सेथियन 1988 के कारण है। हालांकि, मूल्यों के घने डी-आयामी सरणी डेटा संरचना के माध्यम से सीधा कार्यान्वयन, परिणाम समय और भंडारण जटिलता दोनों में होता है $O(n^{d})$, कहाँ पे $n$ डोमेन के स्थानिक विस्तार का क्रॉस सेक्शनल रिज़ॉल्यूशन है और $d$ डोमेन के स्थानिक आयामों की संख्या है।

संकीर्ण बैंड

नैरो बैंड लेवल सेट विधि, 1995 में एडालस्टीनसन और सेथियन द्वारा शुरू की गई, अधिकांश संगणनाओं को इंटरफ़ेस के आसपास के सक्रिय स्वरों के एक पतले बैंड तक सीमित कर दिया, इस प्रकार तीन आयामों में समय की जटिलता को कम कर दिया $O(n^{2})$ अधिकांश ऑपरेशनों के लिए। सक्रिय स्वरों की सूची को फिर से बनाने के लिए नैरोबैंड संरचना के आवधिक अद्यतन की आवश्यकता थी, जिसके लिए एक आवश्यक था $O(n^{3})$ ऑपरेशन जिसमें पूरे वॉल्यूम पर वोक्सल्स एक्सेस किए गए थे। इस नैरोबैंड योजना के लिए भंडारण जटिलता अभी भी थी $O(n^{3}).$ संकीर्ण बैंड डोमेन एज पर डिफरेंशियल कंस्ट्रक्शन को समाधान को स्थिर करने के लिए सावधानीपूर्वक प्रक्षेप और डोमेन परिवर्तन योजनाओं की आवश्यकता होती है।

विरल क्षेत्र

इस $O(n^{3})$ 1998 में व्हिटेकर द्वारा शुरू की गई अनुमानित विरल क्षेत्र स्तर सेट पद्धति में समय की जटिलता को समाप्त कर दिया गया था। इंटरफ़ेस के चारों ओर सक्रिय स्वरों को ट्रैक करने के लिए विरल फ़ील्ड स्तर सेट विधि लिंक्ड सूचियों के एक सेट को नियोजित करती है। यह किसी भी महत्वपूर्ण ओवरहेड के बिना आवश्यकतानुसार सक्रिय क्षेत्र के वृद्धिशील विस्तार की अनुमति देता है। जबकि लगातार $O(n^{2})$ समय में कुशल, $O(n^{3})$ भंडारण स्थान अभी भी विरल क्षेत्र स्तर सेट विधि द्वारा आवश्यक है। देखना कार्यान्वयन विवरण के लिए।

विरल ब्लॉक ग्रिड

स्पार्स ब्लॉक ग्रिड विधि, 2003 में ब्रिडसन द्वारा शुरू की गई, आकार के पूरे बाउंडिंग वॉल्यूम को विभाजित करता है $n^{3}$ के छोटे घन ब्लॉकों में $m^{3}$ स्वर प्रत्येक। आकार का एक मोटा ग्रिड $(n/m)^{3}$ फिर पॉइंटर्स को केवल उन ब्लॉकों में संग्रहीत करता है जो स्तर सेट के संकीर्ण बैंड को पार करते हैं। ब्लॉक आवंटन और डीलोकेशन घटित होते हैं क्योंकि सतह विकृतियों को समायोजित करने के लिए फैलती है। इस पद्धति में एक उप-इष्टतम भंडारण जटिलता है $O\left((nm)3+m^{3}n^{2}\right)$, लेकिन सघन ग्रिडों में निहित निरंतर समय पहुंच को बरकरार रखता है।

अष्टक

1999 में स्ट्रेन द्वारा शुरू की गई ऑक्ट्री लेवल सेट विधि और लोसासो, गिबू और फेडकीव द्वारा परिष्कृत, और हाल ही में मिन और गिबू द्वारा नेस्टेड क्यूब्स के पेड़ का उपयोग करता है जिसमें पत्ती नोड्स में हस्ताक्षरित दूरी मान होते हैं। पर्याप्त सटीकता प्राप्त करने के लिए वर्तमान में ऑक्ट्री स्तर के सेट को इंटरफ़ेस (यानी संकीर्ण बैंड) के साथ एक समान शोधन की आवश्यकता होती है। भंडारण के मामले में यह प्रतिनिधित्व कुशल है, $O(n^{2}),$ और एक्सेस प्रश्नों के मामले में अपेक्षाकृत कुशल, $O(\log \,n).$ ऑक्ट्री डेटा संरचनाओं पर स्तर विधि का एक लाभ यह है कि कोई आंशिक अंतर समीकरणों को हल कर सकता है जो विशिष्ट मुक्त सीमा समस्याओं से जुड़ा होता है जो स्तर सेट पद्धति का उपयोग करते हैं। CASL अनुसंधान समूह कम्प्यूटेशनल सामग्री, कम्प्यूटेशनल द्रव गतिकी, इलेक्ट्रोकाइनेटिक्स, छवि निर्देशित सर्जरी और नियंत्रण में काम की इस पंक्ति को विकसित किया है।

रन-लम्बाई एन्कोडेड

रन-लम्बाई एन्कोडिंग (आरएलई) स्तर सेट विधि, 2004 में पेश की गई, संकरे बैंड को पूर्ण सटीकता के साथ संग्रहीत करते समय संकीर्ण बैंड से दूर क्षेत्रों को केवल उनके संकेत प्रतिनिधित्व के लिए संपीड़ित करने के लिए RLE योजना लागू करता है। संकीर्ण बैंड का अनुक्रमिक ट्रैवर्सल इष्टतम है और ऑक्ट्री स्तर सेट पर भंडारण दक्षता में और सुधार हुआ है। एक त्वरण लुकअप तालिका के अतिरिक्त तेजी के लिए अनुमति देता है $O(\log r)$ रैंडम एक्सेस, जहां आर प्रति क्रॉस सेक्शन रन की संख्या है। आरएलई योजना को एक आयामी पुनरावर्ती फैशन में लागू करके अतिरिक्त दक्षता प्राप्त की जाती है, नीलसन और मुसेथ के समान डीटी-ग्रिड द्वारा पेश की गई एक तकनीक।

हैश टेबल स्थानीय स्तर सेट

हैश टेबल लोकल लेवल सेट मेथड, 2011 में आईयुरेक्ली और ब्रीन द्वारा पेश किया गया और 2012 में ब्रून, गुइटेट और गिबू द्वारा विस्तारित किया गया, इंटरफ़ेस के चारों ओर एक बैंड में केवल स्तर सेट डेटा की गणना करता है, जैसा कि नैरो बैंड लेवल-सेट विधि में है, लेकिन डेटा को केवल उसी बैंड में संग्रहीत करता है। एक हैश तालिका डेटा संरचना का उपयोग किया जाता है, जो प्रदान करता है $O(1)$ डेटा तक पहुंच। हालांकि, ब्रून एट अल। निष्कर्ष निकालते हैं कि उनकी विधि, लागू करने में आसान होने के बावजूद, क्वाडट्री कार्यान्वयन से भी बदतर प्रदर्शन करती है। वे पाते हैं

as it is, [...] a quadtree data structure seems more adapted than the hash table data structure for level-set algorithms.

खराब दक्षता के तीन मुख्य कारण सूचीबद्ध हैं:

1. सटीक परिणाम प्राप्त करने के लिए, इंटरफ़ेस के करीब एक बड़े बैंड की आवश्यकता होती है, जो इंटरफ़ेस से दूर ग्रिड नोड्स की अनुपस्थिति का प्रतिकार करता है;
2. स्थानीय ग्रिड के बाहरी किनारों पर एक्सट्रपलेशन प्रक्रियाओं से प्रदर्शन बिगड़ जाता है और
3. बैंड की चौड़ाई समय कदम को सीमित करती है और विधि को धीमा कर देती है।

बिंदु आधारित

2005 में कॉर्बेट पॉइंट-बेस्ड लेवल सेट मेथड पेश किया। स्तर सेट के एक समान नमूने का उपयोग करने के बजाय, निरंतर स्तर सेट फ़ंक्शन को असंगठित बिंदु नमूनों के सेट से कम से कम वर्गों के माध्यम से पुनर्निर्माण किया जाता है।

इस पेज में लापता आंतरिक लिंक की सूची

• लेवल सेट
• प्रतिपादन (कंप्यूटर ग्राफिक्स)
• वॉक्सेल
• रन-लेंथ एन्कोडिंग
• कम से कम वर्ग चल रहा है