यह निर्धारित करने के लिए कि क्या दो परिपत्र क्षेत्र एक दूसरे के साथ ओवरलैप करते हैं

Question

प्रत्येक क्षेत्र को (x, y, r, a, d) के रूप में प्रदर्शित किया जा सकता है, जहां x, y स्थान है, आर त्रिज्या है, डी दिशा है, और एक कोण है। दो परिपत्र क्षेत्रों की इन जानकारी को देखते हुए, यह निर्धारित करने के लिए कि क्या वे एक दूसरे के साथ ओवरलैप करते हैं? क्या इसे हल करने के लिए कोई कुशल एल्गोरिदम है? धन्यवाद!

Answer 1

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

दो केंद्रों के बीच की दूरी का काम करें और फिर, यदि यह त्रिज्या के योग से अधिक है, तो कोई टक्कर नहीं हो सकती है। दक्षता के लिए, वर्गमूल का उपयोग नहीं करते, बस सीधे वर्ग मूल्यों पर काम:

if (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) > (r1 + r2) * (r1 + r2): 
    # No chance of collision. 

इसे बाहर काम करते हुए सर्कल क्षेत्रों के लिए एक छोटे से मुश्किल हो जाएगा।

---

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

यदि यह मामला था, तो मैं आर्क को सीधे रेखाओं की एक श्रृंखला में बदलने में देखता हूं (जिसकी संख्या शायद a पर निर्भर करती है, चाप के "फैल" - आप शायद एक से दूर हो सकते हैं चाप के एक डिग्री के फैलाव के लिए कुछ लाइनें लेकिन यह 180 डिग्री के लिए बहुत अच्छी तरह से काम नहीं करेगी)।

सीधे लाइन टकराव का पता लगाना एक बेहतर ज्ञात तरीका है हालांकि आपको इस तथ्य से निपटना होगा कि तुलना की संख्या तेजी से बढ़ सकती है।

---

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

सबसे पहले, उस मामले को पहचानने के लिए ऊपर की जांच करें जहां कोई टकराव संभव नहीं है। यदि सर्किलों के बीच कोई टकराव संभव नहीं है, तो न तो arcs टकरा सकते हैं।

दूसरा, जांच करें कि मंडलियों में एक टकराव बिंदु है या नहीं। यही मामला है:

(x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) == (r1 + r2) * (r1 + r2) 

निश्चित रूप से उपयुक्त त्रुटि सीमा के भीतर। हमें अब सभी को पता होना चाहिए कि समानता के लिए फ़्लोटिंग पॉइंट नंबरों की तुलना करना किसी प्रकार की डेल्टा तुलना का उपयोग करना चाहिए।

यदि ऐसा है, तो आपके पास एक बिंदु जांचने के लिए है और आप आसानी से उस बिंदु को पा सकते हैं। यह बात सीधी रेखा (x1,y1) से (x2,y2) करने के लिए या प्रमुख के साथ r1 इकाइयों है कि रेखा के साथ कुछ अंश जाने के रूप में इसे देख:

(x1 + (x2-x1) * (r1+r2)/r1, y1 + (y2-y1) * (r1+r2)/r1) 

अन्यथा, वहाँ दो अंक जाँच करने के लिए और आप एक के जवाब का उपयोग कर सकते हैं this one जैसे प्रश्न यह निर्धारित करने के लिए कि वे दो बिंदु क्या हैं।

एक बार जब आप कुछ टक्कर अंक है, यह उन बिंदुओं एक चाप पर कर रहे हैं पता लगाने के लिए एक much simpler method है, याद रखें कि इस उम्मीदवार बिंदु, उन्हें टकराने के लिए दोनों आर्क्स पर होने की आवश्यकता होगी सिर्फ एक पर नहीं ।

Answer 2

चूंकि हमारे पास परिपत्र क्षेत्र हैं, कोण और दिशा इससे कोई फर्क नहीं पड़ता कि आप वास्तविक समय में ऐसा कर रहे हैं। निम्नलिखित केवल पूर्ण सर्कल क्षेत्रों पर लागू होता है, या यदि दोनों क्षेत्र एक-दूसरे को इंगित कर रहे हैं।

आप अगले चरणों का पालन कर सकते हैं:

1) प्रत्येक क्षेत्र के बीच की दूरी का पता लगाएं, 2) कि दूरी के दोनों त्रिज्या घटाएँ, 3) यदि परिणाम नकारात्मक है, वहाँ दोनों के बीच एक टकराव हो गया है क्षेत्रों। अन्यथा, यह टकराव की दूरी है।

उदाहरण के लिए, हमारे पास 50 इकाई त्रिज्या दोनों के साथ दो सेक्टर हैं। उनके केंद्र बिंदुओं के बीच की दूरी 80 है। 80-50-50 = -20 घटाएं, इसलिए आप जानते हैं कि दूरी में 20 इकाइयां टक्कर आई हैं।

अन्यथा, यदि दूरी 500, 500-50-50 = 400, सकारात्मक मूल्य थी, अब आप जानते हैं कि ये दो क्षेत्र 400 इकाइयां अलग हैं।

अब, यदि मंडल बहुत करीब हैं, तो कहें, 1 इकाई अलग, 1-50-50 = -99, जिसका अर्थ है कि वे लगभग पूरी तरह ओवरलैपिंग कर रहे हैं।

सच सेगमेंट सर्कुलर सेक्टर जो आपने टिप्पणियों पर निर्दिष्ट किया है, आपको पैक्सडीब्लोस या मैक के उत्तरों का उपयोग करना चाहिए।

Answer 3

दो चरण हैं। सबसे पहले यह पता लगाने की अगर दो केन्द्रों पर्याप्त एक दूसरे के करीब एक टक्कर है, जो उनकी त्रिज्या के योग के उनके बीच की दूरी की तुलना द्वारा किया जा सकता है की अनुमति के लिए कर रहे हैं:

if (((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) > ((r1 + r2) * (r1 + r2))) 
    // No collision. 

तो फिर तुम कि क्या जांच करने की आवश्यकता केन्द्रों के बीच की रेखा आर्क्स अपने विभिन्न कोणों से परिभाषित किया गया दायरे में आता है:

float angle1to2 = Math.atan2(y2 - y1, x2 - x1); 
if (angle1to2 < (d1 - a1/2) || angle1to2 > (d1 + a1/2)) 
    // No collision 
float angle2to1 = angle1to2 + Math.PI; 
if (angle2to1 < (d2 - a2/2) || angle2to1 > (d2 + a2/2)) 
    // No collision 

आप बाहर रखा जा रहा है एक टक्कर की संभावना के बिना इन चेकों के माध्यम से प्राप्त है, तो आप को सफलतापूर्वक एक टक्कर का पता चला है।

चेतावनी: इस कोड का परीक्षण बिल्कुल नहीं किया गया है। विशेष रूप से, atan2 कॉल को आपके समन्वय प्रणाली के आधार पर कुछ tweaking की आवश्यकता हो सकती है।

संपादित करें: ने महसूस किया कि यह एक महत्वपूर्ण कोने का मामला याद करता है, जहां आर्क एक दूसरे पर "पॉइंटिंग" नहीं कर रहे हैं लेकिन फिर भी ओवरलैप हैं। इस पर ruminate और वापसी ...