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

Question

मैं युवा वयस्कों के लिए टकराव का पता लगाने वाला गेम ट्यूटोरियल तैयार कर रहा हूं, इसलिए मैं इसे समझाना आसान बनाने के लिए जितना संभव हो उतना सरल होना चाहता हूं।

आवश्यकताएं बहुत सरल हैं। दुनिया 2 डी है और इसमें केवल आयतों (मनमानी आकारों) शामिल हैं। बीएसपी और यहां तक ​​कि क्वाड्रिस ऐसा लगता है जैसे यह अधिक होगा (फिर से, सादगी पर जोर दिया जाता है) लेकिन मैं सभी एन (एन -1)/2 संभावित टकरावों के माध्यम से मजबूती से बलपूर्वक कुछ और कुशल बनाना चाहता हूं।

2 डी, आयत केवल, और सरल।

क्या कोई भी एल्गोरिदम को इंगित कर सकता है जिसे मैं देख सकता हूं? क्या मैं एक क्वाड्री एल्गोरिदम हूं जिसे मैं ढूंढ रहा हूं?

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

Answer 1

मेरे अनुभव में, सभी ब्रॉडफेस टकराव-पहचान एल्गोरिदम अपेक्षाकृत सूक्ष्म और समझने में कठोर हैं। यह देखते हुए कि सस्ते आयताकार टक्कर परीक्षण कितना है, मैं एन^2 एल्गोरिदम का उपयोग करके पाठ को ढूढ़ूंगा, फिर बोनस सामग्री के रूप में, शायद स्थानिक इंडेक्सिंग का विचार पेश कर सकता है। सैकड़ों आयताकारों के साथ, मैं शर्त लगाऊंगा कि गूंगा रास्ता पर्याप्त तेज़ है।

आपके उद्देश्यों के लिए एक क्वाड्री ठीक होगा, लेकिन याद रखें कि जब आप गैर-बिंदुओं से निपट रहे हैं, तो आपको आयताकार को उस नोड में रखना होगा जिसमें सभी क्वाड्रंट्स शामिल हों। फिर, जब कम नोड में कुछ ऐसा परीक्षण किया जाता है, तो आपको उस नोड में और उसके सभी पूर्वजों के सभी अंगों के खिलाफ परीक्षण करना होगा!

आप एक प्रकार और स्वीपर एल्गोरिदम पर भी विचार कर सकते हैं, क्योंकि जो आप पहले से प्राप्त कर चुके हैं वह धुरी-गठबंधन बाध्यकारी बक्से हैं।

Answer 2

एक सरल रणनीति है कि एक साधारण 2 डी खेल में एक प्रारंभिक प्रयास में पता लगाने के तेज अब dimension.The टक्कर चरण के अनुसार क्रमबद्ध एक सूची बनाए रखना था कुछ इस तरह थे:

for i in 0..n 
    j = i+1 
    while rect[j].left < rect[i].right 
     check for collision in y 
     j=j+1 
    endwhile 
endfor 

Answer 3

यहाँ एक सरल है एल्गोरिदम जो चीजों को थोड़ा सा गति देगा और अक्ष-संरेखित आयताकारों पर काम करेगा।

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

सभी प्रविष्टि और निकास बिंदुओं की एक क्रमबद्ध सूची बनाएं।

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

फिर आप पाठक को उस अभ्यास के माध्यम से चल सकते हैं जिसमें "प्रवेश" सूची स्वयं वाई-अक्ष पर "एंटर" और "निकास" बिंदुओं के साथ वाई-अक्ष पर क्रमबद्ध होती है।