एक-आयामी टकराव का पता लगाने के लिए सबसे अच्छा तरीका क्या है?

Question

मैं सिमुलेशन सॉफ्टवेयर का एक टुकड़ा लिख ​​रहा हूं, और एक लाइन के साथ टक्कर के परीक्षण के लिए एक कुशल तरीका की आवश्यकता है।

सिमुलेशन एक ट्रैक पर कई स्विच पार करने वाली ट्रेन का है। जब एक पहिया स्विच के एन इंच के भीतर आता है, तो स्विच चालू हो जाता है, फिर पहिया छोड़ने पर बंद हो जाता है। चूंकि सभी पहियों एक ही आकार के होते हैं, और सभी स्विच एक ही आकार के होते हैं, मैं ट्रैक के साथ एक समन्वय एक्स के रूप में उनका प्रतिनिधित्व कर सकता हूं। एक बार सेट करने के बाद स्विच दूरी और पहिया दूरी एक-दूसरे के संबंध में नहीं बदलती हैं।

सूचियों में एक्स निर्देशांक रखकर और उन्हें घुमाकर ब्रूट फोर्स के माध्यम से किया जाने पर यह काफी मामूली समस्या है, लेकिन मुझे इतना कुशलता से करने का एक तरीका चाहिए, क्योंकि यह बेहद सटीक होना चाहिए, भले ही ट्रेन उच्च गति पर चल रहा है। 2 डी टक्कर पहचान पर ट्यूटोरियल का एक टन है, लेकिन मुझे यकीन नहीं है कि इस अद्वितीय 1 डी परिदृश्य के बारे में जाने का सबसे अच्छा तरीका है।

---

जाहिर है कि मेरा डेटा कैसा दिखता है इसके बारे में कुछ भ्रम है।

मैं एक ही साइट का अनुकरण कर रहा हूं, पूरे क्षेत्र में नहीं। ट्रेनें विभिन्न प्रकार की कारों के साथ किसी भी लंबाई की हो सकती हैं, लेकिन केवल एक ही ट्रेन है। मेरा ट्रेन डेटा {48,96,508,556,626,674,...} रूप में है, जो रेल के सामने (0) से धुरी के केंद्र में दूरी दर्शाता है।

(ट्रेन डेटा अधिक होने की संभावनाCarवस्तुओं, जिनमें से प्रत्येक लंबाई और कहा कि कार के सामने से धुरा दूरी का प्रतिनिधित्व पूर्णांकों की एक सूची है की एक आदेश दिया सूची के रूप में मेरे पास आते हैं, लेकिन यह सभी एक ही सूची में एकत्र हो जाते हैं, क्योंकि सभी धुरी मेरे लिए समान हैं।)

मेरे स्विच सभी सौ फुट के भीतर हैं, और अक्सर पूरी तरह से ट्रेन द्वारा कवर किया जाएगा, स्विच किसी भी अंतराल पर हो सकते हैं सैकड़ों फीट कई इंच अलग हैं, और ट्रेन के समान रूप में हैं: {0,8,512,520,...}, साइट की शुरुआत से दूरी को स्विट के केंद्र में इंगित करता है एच।

अंत में, मुझे पता है कि पहिया इंच में स्विच को सक्रिय करता है।

उदाहरण के लिए, उपर्युक्त नमूना डेटा और 8 इंच की सक्रियण दूरी का उपयोग करते हुए, एक्स = 0 पर पहला स्विच सक्रिय होगा जब ट्रेन एक्स = 40 हिट करेगी, जिसका अर्थ है कि ट्रेन साइट पर 40 इंच है। जब ट्रेन एक्स = 48 हिट करती है, एक्स = 8 पर स्विच भी सक्रिय होता है। एक्स = 56 पर, पहला स्विच बंद हो जाता है, और एक्स = 64 पर, दूसरा स्विच भी बंद हो जाता है। अलग-अलग धुरी साइट को पार करते समय अलग-अलग स्विच चालू और बंद कर रहे हैं।

ट्रेन आमतौर पर 10 मील प्रति घंटे की रफ्तार से चल रही है, लेकिन बहुत अधिक जा सकती है। (अभी हमारे सिमुलेशन 30 मील प्रति घंटे तक ही सीमित कर रहा है, लेकिन उच्च बहुत अच्छा होगा।)

Answer 1

ट्रैक सेगमेंट की सूची में अपने स्विच स्थानों और संवेदनशीलता सीमा को प्री-प्रोसेस करें। प्रत्येक खंड में लंबाई होती है, और प्रत्येक सेगमेंट के बीच 'ऑन' या 'ऑफ' ईवेंट स्विच का एक सेट होता है।

switch_on (0), (length: 8), switch_on (1), // x = zero here 
segment (length: 8), switch_off (0), 
segment (length: 8), switch_off (1), 
segment (length: 488), switch_on (2), 
segment (length: 8), switch_on (3), 
segment (length: 8), switch_off (2), 
segment (length: 8), switch_off (3), 
... 

प्रत्येक धुरी के लिए, इसका वर्तमान स्थान ट्रैक ट्रैक सेगमेंट के साथ भी प्रदर्शित होता है।

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

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

यदि आप एक निश्चित समय चरण सिमुलेशन पर हैं, तो चरण के अंत में उस समय तक होने वाली सभी घटनाओं को संसाधित करें, फिर एक घटना धुरी को उस बिंदु तक ले जाने के लिए जब वे अंत तक पहुंच जाएंगे कदम।

Answer 2

सभी स्विच 'निर्देशांकों का एक क्रमबद्ध सूची है और निकटतम स्विच खोजने के लिए सूची पर द्विआधारी खोज का उपयोग करें। फिर यह देखने के लिए जांचें कि यह कितना दूर है और चाहे वह टकराव हो या नहीं।

हे (लॉग एन)

एक अन्य विकल्प तथ्य यह है कि ट्रैक के साथ ट्रेन चाल और भी है तो केवल दो स्विच, पीछे एक और एक आगे के करीब आ सकते हैं फायदा उठाने के लिए है।

सभी स्विचों की दोगुनी-लिंक्ड सूची बनाएं और लिंक की गई सूची में सही स्थान पर ट्रेन का प्रतिनिधित्व करने के लिए अतिरिक्त नोड रखें। फिर ट्रेन की ओर बढ़ने वाले स्विच के निकटता की जांच करें।

हे (1)

बचाने के लिए स्मृति, एक सरणी में अनुसार क्रमबद्ध निर्देशांक की दुकान और बस ट्रैक जो इंडेक्सों का ट्रेन के बीच है रहते हैं।

Answer 3

स्विच सूची को बेन द्वारा इंगित एक दोगुनी-लिंक्ड सूची के रूप में स्टोर करें।

अगले स्विच और आपके वर्तमान स्थिति से संबंधित पिछले स्विच में व्हील ऑब्जेक्ट (या संरचना, मानते हुए एक है) में एक पॉइंटर रखें। इन्हें घुमाएं क्योंकि पहिया ट्रैक पर रखा गया है।

जैसे ही आप प्रत्येक स्विच पर जाते हैं, नए "अगले" और "पिछले" के लिए अपने व्हील ऑब्जेक्ट में "अगला" और "पिछला" स्विच स्वैप करें जिसे दोगुनी-लिंक्ड सूची की जांच करके जल्दी से प्राप्त किया जा सकता है।

यह पहिया की संभावित प्रारंभिक नियुक्ति को छोड़कर, सभी खोजों से बचाता है।

इसके अतिरिक्त, "स्विच" संरचना का उपयोग निकटवर्ती सूचक को उन सभी पहियों पर वापस रखने के लिए किया जा सकता है जो इसे "पिछला" या "अगला" के रूप में सूचीबद्ध करते हैं। (यहां एक म्यूटेक्स है, इसलिए इस बारे में सावधान रहें कि यह कौन अपडेट करता है।) यह किसी भी दिए गए स्विच और उसके दूरी से आने वाले लोगों के त्वरित अपडेट प्रदान कर सकता है।

Answer 4

मानते हैं कि एक्सेल-टू-एक्सल दूरी हमेशा सक्रियण दूरी से अधिक होती है, और ट्रेन प्रवेश के बाद अक्सर मार्ग बदल नहीं जाते हैं, तो आप चीजों को पूर्व-गणना के साथ गति में सक्षम करने में सक्षम होना चाहिए। असल में, प्रत्येक स्विच के लिए, ट्रेन यात्रा दूरी की एक सूची की गणना करें जिस पर यह टॉगल करेगा, फिर ट्रेनों की प्रगति के रूप में सूचियों के माध्यम से चलें।

स्यूडोकोड:

axles = {48,96,508,556,626,674,...} 
switches ={0,8,512,520,...} 
activate = 8 
float toggledist[num_switches] 
boolean switchState[num_switches]={false,false,false,...} 
int idx[num_switches] 

for (i in switches) 
    n = 0 
    for (a in axles) 
    toggledist[n++] = switches[i]+axles[a]-activate 
    toggledist[n++] = switches[i]+axles[a]+activate 

travel= 0.0f; 

each (cycle) 
    travel += TrainVelocity*time; 
    for (i in switches) 
    while (trigger>=toggledist[idx[i]]) 
     switchState[i]=!switchState[i]; 
     //additional processing for switch change here, if needed 
     idx[i]++;