2 डी स्थानिक अनुक्रमण प्रश्न:एक अनंत स्केलेलेस क्वाड्री क्या कहा जाता है?
क्या आप एक डेटा संरचना अनिवार्य रूप से है कि एक अनंत * quadtree जिसका नोड्स न निरपेक्ष निर्देशांक और न ही पूर्ण तराजू शामिल कहते हैं - जिसमें प्रत्येक नोड के समन्वय प्रणाली इकाई के लिए सामान्यीकृत किया जा चुका वर्ग (0,0) - (1,1), और जिसमें शीर्ष-स्तरीय नोड बिल्कुल ठीक नहीं है?
यह निश्चित रूप से एक क्वाड्री है - लेकिन क्वाड्री के प्रकार क्या है? (क्या कोई आम नाम है? मैंने साहित्य में नामित और परिभाषित दर्जनों प्रकार के क्वाड्रिस को देखा है, लेकिन यह विशेष नहीं है।)
एक दृश्य प्रस्तुत करने के लिए, आपको कुछ प्रारंभिक नोड दिया जाता है (जरूरी नहीं कि रूट), इसका आकार पिक्सेल में है, और स्क्रीन पर इसका स्थान है। फिर आप नोड के भीतर सभी ऑब्जेक्ट्स को वर्तमान रूपांतरण मैट्रिक्स का उपयोग करके अपने निर्देशांक स्केल करके खींचते हैं, जिसे आप पेड़ के नीचे जाने के दौरान ढेर और हिस्सों पर धक्का देते हैं। नोड्स के पूर्ण निर्देशांक इस प्रकार उपलब्ध हैं, हालांकि प्रतिपादन के दौरान अस्थायी कार्य चर, और डेटा संरचना के भीतर ही शामिल नहीं हैं।
यदि नोड के अंदर कोई ऑब्जेक्ट नोड के बाहर चला जाता है (उदाहरण के लिए, इकाई वर्ग के बाहर), तो आप इसे किसी अन्य नोड को पुन: असाइनमेंट के लिए माता-पिता को पास कर देते हैं। यदि कोई वस्तु खंडित हो जाती है (उदाहरण के लिए, बुलेट द्वारा मारा गया क्षुद्रग्रह), छोटे भाग बच्चों के नोड्स को पारित किए जाते हैं, जिन्हें प्रत्येक नोड के भीतर यूनिट-स्क्वायर सामान्यीकरण को बनाए रखने के लिए उचित निर्देशांक को स्केल करना होगा।
स्थानिक इंडेक्सिंग में उपयोग किए जाने वाले परंपरागत क्वाड्री कार्यान्वयन से यहां महत्वपूर्ण अंतर यह है कि वस्तुओं के निर्देशांक हमेशा नोड के समन्वय तंत्र से संबंधित होते हैं, जिसमें वे शामिल होते हैं। यह सापेक्षता न केवल स्थिति के लिए बल्कि स्केल करने के लिए भी लागू होती है।
* पूर्ण निर्देशांक की कमी के लिए अनंत; यहां तक कि डबल-प्रेसिजन फ़्लोटिंग-पॉइंट निर्देशांक पूर्ण स्थिति के लिए उपयोग किए जाने पर स्थिति और आकार पर सीमा प्रदान करते हैं।
फ्रेड? (मजाक कर रहा हूं)। – bmargulies