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

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

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

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

शक्तिशाली स्तर-समुच्चय विधि स्टेनली ओशर और जेम्स सेथियन 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)$ रैंडम एक्सेस की अनुमति देता है, जहां 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 में कॉर्बेट पॉइंट-बेस्ड लेवल समुच्चय मेथड पेश किया। स्तर समुच्चय के एक समान नमूने का उपयोग करने के बजाय, निरंतर स्तर समुच्चय फ़ंक्शन को असंगठित बिंदु नमूनों के समुच्चय से कम से कम वर्गों के माध्यम से पुनर्निर्माण किया जाता है।

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

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