आंकड़ा संरचना और कलन विधि अनियमित आकार चलती की टक्कर का पता लगाने के वस्तुओं

Question

मैं इस साक्षात्कार सवाल

कई अनियमित आकार की वस्तुओं यादृच्छिक दिशाओं में आगे बढ़ रहे हैं भर में आया था। टकराव का पता लगाने के लिए एक डेटा संरचना और एल्गोरिदम प्रदान करें। याद रखें कि वस्तुओं की संख्या लाखों में है।

मुझे लगता है कि प्रत्येक ऑब्जेक्ट में एक्स और वाई समन्वय होगा। अन्य मान्यताओं का स्वागत है। मुझे लगता है कि पेड़ का एक निश्चित प्रकार भी इस्तेमाल किया जाना चाहिए, लेकिन मैं एल्गोरिदम के बारे में अनजान हूं।

कोई सुझाव?

Answer 1

मैं Plane Sweep Algorithm या Bently-Ottmann Algorithm पर एक नज़र होगा। यह O(n log(n)) समय (और O(n) अंतरिक्ष) में निर्धारित करने के लिए विमान स्वीप का उपयोग करता है जो यूक्लिडियन विमान पर लाइनों का चौराहे है।

Answer 2

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

For each irregular shaped object1  

int left1, left2; 
int right1, right2; 
int top1, top2; 
int bottom1, bottom2; 
bool bRet = 1; // No collision 

left1 = object1->x; 
right1 = object1->x + object1->width; 
top1 = object1->y; 
bottom1 = object1->y + object1->height; 

For each irregular shaped object2 
{ 
    left2 = object2->x; 
    right2 = object2->x + object2->width; 
    top2 = object2->y; 
    bottom2 = object2->y + object2->height; 

    if (bottom1 < top2) bRet =0; 
    if (top1 > bottom2) bRet = 0; 

    if (right1 < left2) bRet = 0; 
    if (left1 > right2) bRet = 0; 
} 

return bRet; 

Answer 3

इस समस्या के कई समाधान हैं। पहला: बाध्यकारी बक्से या सर्कल (3 डी में गेंदों) का प्रयोग करें। यदि बाउंडिंग बॉक्स अंतर नहीं करते हैं तो आगे कोई परीक्षण की आवश्यकता नहीं है। दूसरा: अपनी जगह को विभाजित करें। आपको अन्य ऑब्जेक्ट्स के खिलाफ हर ऑब्जेक्ट का परीक्षण करने की आवश्यकता नहीं है (वह ओ (एन^2) है)। आप quadtrees के साथ ओ (एन) की औसत जटिलता हो सकती है।

Answer 4

संभवतया आप जो चाहते हैं वह विमान को एक-जेड-वक्र या हिल्बर्ट-वक्र जैसे अंतरिक्ष-भरने-वक्र के साथ विभाजित करना है और इस प्रकार 2 डी समस्या की जटिलता को 1 डी समस्या में कम करना है। Quadtree के लिए देखो।

लिंक: http://dmytry.com/texts/collision_detection_using_z_order_curve_aka_Morton_order.html