में स्थानिक डेटा संरचनाएं मैं उच्च प्रदर्शन क्लस्टर पर सैद्धांतिक रसायन शास्त्र में काम करता हूं, जिसमें अक्सर आणविक गतिशीलता सिमुलेशन शामिल होते हैं। मेरे काम के पते में से एक समस्या में एन-आयामी (आमतौर पर एन = 2-5) हाइपर-गोलाकार का स्थिर क्षेत्र शामिल होता है, जिसमें एक परीक्षण कण टकरा सकता है। मैं गोलाकार के क्षेत्र का प्रतिनिधित्व करने के लिए उपयोग की जाने वाली डेटा संरचना को अनुकूलित (पढ़ना: ओवरहाल) करना चाहता हूं ताकि मैं तेजी से टकराव का पता लगा सकूं। वर्तमान में मैं एन-यादगार संरचना (केंद्र के प्रत्येक समन्वय के लिए युगल) और निकटतम पड़ोसी सूची में पॉइंटर्स की एक मृत साधारण सरणी का उपयोग करता हूं। मैंने ऑक्टेट- और क्वाड-पेड़ों के बारे में सुना है लेकिन उन्हें एक स्पष्ट स्पष्टीकरण नहीं मिला है कि वे कैसे काम करते हैं, एक को कुशलतापूर्वक कार्यान्वित कैसे करें, या फिर एक के साथ तेजी से टक्कर का पता लगाने के लिए कैसे करें। मेरे सिमुलेशन के आकार को देखते हुए, स्मृति (लगभग) कोई वस्तु नहीं है, लेकिन चक्र हैं।सी
सी
उत्तर
एक क्वाड पेड़ एक 2 आयामी पेड़ है, जिसमें प्रत्येक स्तर पर एक नोड में 4 बच्चे होते हैं, जिनमें से प्रत्येक माता-पिता नोड के क्षेत्रफल के 1/4 को कवर करता है।
एक अक्टूबर का पेड़ एक 3 आयामी पेड़ है, जिसमें प्रत्येक स्तर पर एक नोड में 8 बच्चे होते हैं, जिनमें से प्रत्येक में माता-पिता नोड की मात्रा का 1/8 वां होता है। यहां आपको चित्र देखने में मदद करने के लिए चित्र है: http://en.wikipedia.org/wiki/Octree
यदि आप एन आयामी चौराहे परीक्षण कर रहे हैं, तो आप इसे एन पेड़ में सामान्यीकृत कर सकते हैं।
छेड़छाड़ एल्गोरिदम पेड़ के शीर्ष पर शुरू करके काम करते हैं और किसी भी बच्चे नोड्स में दोबारा घुसपैठ करते हैं जो किसी वस्तु पर परीक्षण किए जाते हैं, किसी बिंदु पर आप पत्ते नोड्स प्राप्त करते हैं, जिसमें वास्तविक वस्तुएं होती हैं।
ऐसा लगता है कि आप kd-tree, को लागू करना चाहते हैं जो आपको एन-आयामी अंतरिक्ष को और अधिक तेज़ी से खोजने की अनुमति देगा। the Stony Brook Algorithm Repository.
पर कार्यान्वयन के लिए कुछ और जानकारी और लिंक हैं क्योंकि आपका क्षेत्र स्थैतिक है (जिसके द्वारा मुझे लगता है कि आप का मतलब है कि हाइपर गोलाकार नहीं चलते हैं), तो सबसे तेज़ समाधान जो मुझे पता है वह एक केडीटी है।
आप अपना खुद का बनाएँ सकते हैं, या किसी और के उपयोग करते हैं, की तरह इस एक: http://libkdtree.alioth.debian.org/
कैसे सबसे अच्छा दृष्टिकोण के लिए अपनी समस्या के लिए यह कई कारकों है कि आप वर्णित नहीं किया है पर निर्भर करता है: - एक ही अति क्षेत्र व्यवस्था होगी कई कण टक्कर गणना के लिए इस्तेमाल किया? - क्या हाइपरफेयर वर्दी आकार हैं? - कण (जैसे सीधी रेखा/वक्र) का आंदोलन क्या है और क्या वह क्षेत्र गोलाकारों से प्रभावित होता है? - क्या आप कण को शून्य मात्रा मानते हैं?
मुझे लगता है कि कण में सरल सीधी रेखा आंदोलन नहीं है क्योंकि यह एक रेखा और बिंदु के बीच निकटतम बिंदु खोजने की अपेक्षाकृत तेज़ गणना होगी, जो कि एक ही गति के बारे में होने की संभावना है बक्से रेखा के साथ छेड़छाड़ (यह निर्धारित करने के लिए कि एन-पेड़ में जांच करने के लिए कहां है)।
यदि आपके हाइपरस्फेयर पदों को बहुत सारे कण टकरावों के लिए ठीक किया गया है तो voronoi decomposition/Dirichlet tessellation की गणना करने से आपको बाद में यह पता चलने का एक तेज़ तरीका मिलेगा कि अंतरिक्ष में किसी भी दिए गए बिंदु के लिए आपके क्षेत्र के निकट क्षेत्र कौन सा क्षेत्र है।
हालांकि octrees/quadtrees/2^n-tree के बारे में आपके मूल प्रश्न का उत्तर देने के लिए, एन आयामों में आप एक (हाइपर) -क्यूब से शुरू करते हैं जिसमें उस स्थान का क्षेत्र होता है जिसमें आप रुचि रखते हैं। इसे उप-विभाजित किया जाएगा 2^एन हाइपरक्यूब यदि आप सामग्री को बहुत जटिल मानते हैं। यह तब तक जारी रहता है जब तक आपके पास पत्ती नोड्स में केवल साधारण तत्व (उदा। एक हाइपरफेयर सेंट्रॉइड) न हो। अब जब एन-पेड़ बनाया गया है तो आप इसे अपने कण के पथ को लेकर और बाहरी हाइपरक्यूब के साथ छेड़छाड़ करके टकराव का पता लगाने के लिए इसका उपयोग करते हैं। चौराहे की स्थिति आपको बताएगी कि पेड़ के अगले स्तर में कौन सा हाइपरक्यूब अगले दौरे के लिए है, और आप उस स्तर पर सभी 2^एन हाइपरक्यूब के साथ छेड़छाड़ की स्थिति निर्धारित करते हैं, जब तक आप एक पत्ता नोड तक नहीं पहुंच जाते। एक बार जब आप पत्ते तक पहुंच जाते हैं तो आप अपने कण पथ और उस पत्ते पर संग्रहीत हाइपरफेयर के बीच बातचीत की जांच कर सकते हैं। यदि आपके पास टकराव है तो आप समाप्त हो गए हैं, अन्यथा आपको वर्तमान हाइपरक्यूब पत्ती से कण पथ का निकास बिंदु ढूंढना होगा और यह निर्धारित करना होगा कि यह कौन सा हाइपरक्यूब आगे बढ़ता है। तब तक जारी रखें जब तक आपको टकराव न हो या पूरी तरह से बाध्यकारी हाइपरक्यूब छोड़ दें।
हाइपरक्यूब से बाहर निकलने पर पड़ोसी हाइपरक्यूब को कुशलतापूर्वक खोजना इस दृष्टिकोण के सबसे चुनौतीपूर्ण हिस्सों में से एक है। 2^एन पेड़ों के लिए समेट के दृष्टिकोण {1, 2} को अनुकूलित किया जा सकता है। केडी-पेड़ (बाइनरी पेड़) के लिए {3} सेक्शन 4.3.3 में एक दृष्टिकोण का सुझाव दिया जाता है।
कुशल कार्यान्वयन प्रत्येक हाइपरक्यूब से अपने बच्चों के हाइपरक्यूब से 8 पॉइंटर्स की सूची संग्रहीत करने के समान सरल हो सकता है, और अगर यह एक पत्ता है (उदाहरण के लिए सभी पॉइंटर्स न्यूल) तो हाइपरक्यूब को विशेष तरीके से चिह्नित करना।
अंतरिक्ष विभाजित करने पर कोई quadtree (जो आप एन-पेड़ के सामान्यीकरण) बनाने के लिए का विवरण क्लिंगर & में पाया जा सकता डायर {4}
के रूप में दूसरों के केडी-पेड़ 2 की तुलना में अधिक अनुकूल हो सकता है उल्लेख किया है^एन-पेड़ आयामों की मनमानी संख्या के विस्तार के रूप में अधिक सरल है, हालांकि वे एक गहरे पेड़ के परिणामस्वरूप होंगे। केडी-पेड़ के साथ अपने हाइपरफेयर की ज्यामिति से मेल खाने के लिए विभाजन स्थिति को अनुकूलित करना भी आसान है। 2^एन पेड़ में टकराव का पता लगाने के ऊपर वर्ण एक केडी-पेड़ पर समान रूप से लागू होता है।
{4} नियमित अपघटन का उपयोग कर चित्र प्रतिनिधित्व में प्रयोगों, क्लिंगर, ए, और डायर, सीआर ई, Comptr। ग्राफिक्स और छवि प्रसंस्करण 5 (1 9 76), 68-105।
एक ऑक्टेट तब तक काम करेगा जब तक आप अपने केंद्रों द्वारा गोलाकार निर्दिष्ट कर सकते हैं - यह पदानुक्रमित रूप से आठ बच्चों के साथ घन क्षेत्रों में अंक डालता है। एक ऑक्टेटरी डेटा संरचना में पड़ोसियों को बाहर करने के लिए आपको गोलाकार-घन गणना (कुछ हद तक देखने के लिए आसान) करने के लिए एक ऑक्टेट में कौन सा घन क्षेत्र क्षेत्र के भीतर होते हैं, इसके लिए आपको आवश्यकता होगी।
निकटतम पड़ोसियों को ढूंढना मतलब है कि जब तक आप एक से अधिक आबादी वाले बच्चे के साथ नोड प्राप्त न करें और आसपास के नोड्स के साथ नोड प्राप्त न हो जाए (यह सुनिश्चित करता है कि क्वेरी सभी तरफ हो जाती है)।
मैं:
स्मृति से, इस (कुछ अनुभवहीन) क्षेत्र-घन चौराहे के लिए बुनियादी एल्गोरिथ्म है। घन के भीतर केंद्र (यह नामित स्थिति हो जाता है)
ii। केंद्र के त्रिज्या आर (क्षेत्र के भीतर कोनों) के भीतर घन के कोने में से कोई भी
iii। क्यूब की प्रत्येक सतह के लिए (आप सतह के किनारे किनारे पर काम कर रहे हैं, यह काम करके कुछ सतहों को खत्म कर सकते हैं) काम करते हैं (यह सब प्रथम वर्ष का वेक्टर अंकगणितीय है):
ए।सतह का एक सामान्य जो क्षेत्र
बी के केंद्र में जाता है। सतह के विमान के साथ क्षेत्र के केंद्र से सामान्य के चौराहे तक दूरी (तार घुमावदार विमान घन की सतह)
सी। विमान का चौराहे घन के किनारे (घन के लिए तार चौराहे की एक शर्त)
iv। तार के आकार की गणना करें (सामान्य लंबाई के अनुपात के कोर^-1 का पाप क्षेत्र के त्रिज्या तक)
v। यदि रेखा पर निकटतम बिंदु तार की दूरी से कम है और बिंदु के बीच बिंदु है रेखा के सिरों को तार के किनारों में से एक को घुमाता है (तार किनारों के किनारे कहीं घन सतह को छेड़छाड़ करता है)।
थोड़ा सा याद किया गया लेकिन यह कुछ ऐसा है जो मैंने एक ऑक्टेटी डेटा संरचना (कई साल पहले) का उपयोग करके गोलाकार क्षेत्रों से जुड़ी स्थिति के लिए किया था। आप केडी-पेड़ों को भी देखना चाहते हैं क्योंकि कुछ अन्य पोस्टर सुझाव देते हैं लेकिन आपका प्रारंभिक प्रश्न मैंने जो किया उसके समान ही लगता है।