यदि मैं आप थे तो मैं एक साधारण बसपा (बाइनरी स्पेस विभाजन) पेड़ को लागू करके शुरू कर दूंगा। चूंकि आप 2 डी में काम कर रहे हैं, बाध्य बॉक्स चेक वास्तव में तेज़ हैं।CBspTree, CBspNode और CBspCut (वास्तव में जरूरत नहीं)
- CBspTree वर्ग CBspNode में से एक रूट नोड उदाहरण है
- CBspNode CBspCut का एक उदाहरण है
- CBspCut का प्रतीक है आप कैसे एक सेट में कटौती: आप मूल रूप से तीन वर्गों की जरूरत है दो अपमान सेट में। यह polymorphism (उदाहरण के लिए सीबीएसपीक्यूएक्स या सीबीएसपीटीयू या कुछ अन्य काटने लाइन) शुरू करके हल किया जा सकता है। CBspCut भी दो CBspNode
विभाजित दुनिया की ओर इंटरफेस पेड़ वर्ग के माध्यम से किया जाएगा और यह एक बहुत अच्छा विचार है कि एक के ऊपर एक अधिक परत बनाने के लिए हो सकता है, इस स्थिति में आप बसपा को प्रतिस्थापित करना चाहते है उदाहरण के साथ समाधान एक चौकोर पेड़ एक बार जब आप इसे लटका रहे हों। लेकिन मेरे अनुभव में, एक बसपा बस ठीक करेगी।
पेड़ में अपने सामान को स्टोर करने के तरीके की विभिन्न रणनीतियां हैं। मेरा मतलब यह है कि आप उदाहरण चुन सकते हैं प्रत्येक नोड में किसी प्रकार का कंटेनर जिसमें उस क्षेत्र पर कब्जा करने वाले ऑब्जेक्ट्स के संदर्भ शामिल हैं। इसका मतलब है (जैसा कि आप स्वयं से पूछ रहे हैं) कि बड़ी चीजें कई पत्तियों पर कब्जा कर लेगी, यानी बड़ी वस्तुओं के कई संदर्भ होंगे और बहुत छोटी चीजें एकल पत्तियों पर दिखाई देंगी।
मेरे अनुभव में इसका बड़ा प्रभाव नहीं है। बेशक यह मायने रखता है, लेकिन आपको यह जांचने के लिए कुछ परीक्षण करना होगा कि यह वास्तव में एक मुद्दा है या नहीं। आप पेड़ में ब्रांडेड नोड्स पर बस उन वस्तुओं को छोड़कर इसे प्राप्त करने में सक्षम होंगे, यानी आप उन्हें "पत्ती के स्तर" पर स्टोर नहीं करेंगे। इसका मतलब है कि पेड़ को घुमाने के दौरान आप उन वस्तुओं को तुरंत पाएंगे।
जब आपके पहले प्रश्न की बात आती है। यदि आप केवल टक्कर परीक्षण के लिए इस उपविभाग का उपयोग करने जा रहे हैं और कुछ और नहीं, तो मैं सुझाव देता हूं कि जो चीजें कभी टकरा नहीं सकतीं वे पेड़ में कभी नहीं डाली जाती हैं। उदाहरण के लिए एक मिसाइल जैसा कि आप कहते हैं, एक और मिसाइल से टकरा नहीं सकता है। इसका मतलब यह होगा कि आपको पेड़ में मिसाइल भी स्टोर नहीं करना है।
हालांकि, आप अन्य चीजों के लिए भी बीएसपी का उपयोग करना चाहेंगे, आपने इसे निर्दिष्ट नहीं किया है लेकिन इसे ध्यान में रखें (माउस को उदास करने के लिए वस्तुओं को चुनने के लिए)। अन्यथा मैं प्रस्ताव करता हूं कि आप बीएसपी में सब कुछ स्टोर करें, और बाद में टकराव को हल करें। संभावित टकराव उम्मीदवारों का सीमित सेट प्राप्त करने के लिए बस एक निश्चित क्षेत्र में ऑब्जेक्ट्स की एक सूची के बीएसपी से पूछें और उसके बाद चेक करें (ऑब्जेक्ट्स को पता है कि वे किसके साथ टकरा सकते हैं, या कुछ अन्य बाहरी तंत्र)।
आप चीजों को तेजी लाने के लिए चाहते हैं, आप भी मर्ज और विभाजित की देखभाल की जरूरत है, यानी जब चीजें पेड़ से निकाल दिए जाते हैं, नोड्स का एक बहुत खाली है या कुछ नीचे मदों की संख्या हो जाएगा कुछ मर्ज थ्रेसहोल्ड के नीचे नोड स्तर कम हो जाएगा। फिर आप दो subtrees सभी वस्तुओं वाले एक नोड में विलय करना चाहते हैं। विभाजन तब होता है जब आप दुनिया में आइटम डालते हैं। तो जब आइटम की संख्या कुछ विभाजन सीमा से अधिक हो जाती है तो आप एक नया कट पेश करते हैं, जो दुनिया को दो में विभाजित करता है। ये मर्ज और विभाजित थ्रेसहोल्ड दो स्थिरांक होना चाहिए जिनका उपयोग आप पेड़ की दक्षता को ट्यून करने के लिए कर सकते हैं।
मर्ज और विभाजन मुख्य रूप से पेड़ को संतुलित रखने के लिए उपयोग किया जाता है और यह सुनिश्चित करने के लिए कि यह अपने विनिर्देशों के अनुसार जितना कुशल हो सके उतना कुशल काम करता है। यह वास्तव में आपको चिंता करने की ज़रूरत है। चीजों को एक स्थान से स्थानांतरित करना और इस प्रकार पेड़ को अद्यतन करना इमो तेज़ है। लेकिन जब विलय और विभाजन की बात आती है तो यह महंगा हो सकता है यदि आप इसे अक्सर करते हैं।
किसी प्रकार की आलसी विलय और विभाजन प्रणाली को पेश करके इसे टाला जा सकता है, यानी आपके पास गंदे झंडे या गिनती को संशोधित करना है। बैच किए जा सकने वाले सभी परिचालनों को बैच करें, यानी 10 वस्तुओं को स्थानांतरित करना और 5 डालना एक बैच हो सकता है।एक बार जब ऑपरेशन का बैच समाप्त हो जाता है, तो आप जांचते हैं कि पेड़ गंदा है और फिर आप आवश्यक विलय और/या विभाजित संचालन करते हैं।
कुछ टिप्पणियां पोस्ट करें यदि आप मुझे आगे बताना चाहते हैं।
चीयर्स!
संपादित
वहाँ कई चीजें हैं जो पेड़ में अनुकूलित किया जा सकता है। लेकिन जैसा कि आप जानते हैं, समयपूर्व अनुकूलन सभी बुराइयों के लिए जड़ है। तो सरल शुरू करें। उदाहरण के लिए, आप कुछ जेनेरिक कॉलबैक सिस्टम बना सकते हैं जिसका उपयोग आप पेड़ को पार करते समय कर सकते हैं। इस तरह आपको बाएं बॉक्स "प्रश्न" से मेल खाने वाली ऑब्जेक्ट्स की एक सूची प्राप्त करने के लिए पेड़ से पूछना नहीं है, इसके बजाय आप केवल पेड़ को पार कर सकते हैं और जब भी आप कुछ हिट करते हैं तो उस कॉल को निष्पादित कर सकते हैं।