math - मैं एक ही विमान में किसी सर्कल और किसी अन्य सर्कल के बीच चौराहे का पता कैसे लगा सकता हूं?




geometry computational-geometry (5)

मैं यह पता लगाने के लिए एक एल्गोरिदम खोज रहा हूं कि एक सर्कल एक ही विमान में किसी अन्य सर्कल के साथ छेड़छाड़ करता है (यह देखते हुए कि विमान में एक से अधिक सर्कल हो सकते हैं)।

एक विधि जो मैंने पाया है वह अलग अक्ष परीक्षण करना है। इसे कहते हैं:

दो ऑब्जेक्ट्स अंतर नहीं करते हैं यदि आप एक ऐसी रेखा पा सकते हैं जो दो ऑब्जेक्ट्स को अलग करती है, यानी एक पंक्ति जैसे कि ऑब्जेक्ट की सभी ऑब्जेक्ट्स या पॉइंट लाइन के विभिन्न किनारों पर हों।

हालांकि, मुझे नहीं पता कि इस मामले को मेरे मामले में कैसे लागू किया जाए।

कोई भी मेरी मदद कर सकता हैं?


एक्सएनए / सी # समाधान

    class Circle
    {
        public Vector2 Center;
        public float Radius;

        public bool Intersects(Circle circle)
        {
            float distanceX = Center.X - circle.Center.X;
            float distanceY = Center.Y - circle.Center.Y;
            float radiusSum = circle.Radius + Radius;
            return distanceX * distanceX + distanceY * distanceY <= radiusSum * radiusSum;
        }
        public bool Contains(Circle circle)
        {
            if (circle.Radius > Radius)
                return false;
            float distanceX = Center.X - circle.Center.X;
            float distanceY = Center.Y - circle.Center.Y;
            float radiusD = Radius - circle.Radius;
            return distanceX * distanceX + distanceY * distanceY <= radiusD * radiusD;
        }
    }

ध्यान दें कि विधि Circle.Intersects () एक सर्कल दूसरे के भीतर होने पर भी सत्य लौटाता है (उन्हें "भरे" सर्किल के रूप में व्यवहार करता है)।


जावा में इस समाधान ने गणितीय विस्तार का उपयोग किया जो ऊपर वर्णित था:

/**
     * 
     * @param values
     *            { x0, y0, r0, x1, y1, r1 }
     * @return true if circles is intersected
     * 
     *         Check if circle is intersect to another circle
     */
    public static boolean isCircleIntersect(double... values) {
        /*
         * check using mathematical relation: ABS(R0-R1) <=
         * SQRT((x0-x1)^2+(y0-y1)^2) <= (R0+R1)
         */
        if (values.length == 6) {
            /* get values from first circle */
            double x0 = values[0];
            double y0 = values[1];
            double r0 = values[2];
            /* get values from second circle */
            double x1 = values[3];
            double y1 = values[4];
            double r1 = values[5];
            /* returun result */
            return (Math.abs(r0 - r1) <= Math.sqrt(Math.pow((x0 - x1), 2)
                    + Math.pow((y0 - y1), 2)))
                    && (Math.sqrt(Math.pow((x0 - x1), 2)
                            + Math.pow((y0 - y1), 2)) <= (r0 + r1));
        } else {
            /* return default result */
            return false;
        }
    }

मैंने यहां दिए गए फॉर्मूला की कोशिश की जो एक अनुमानित उत्तर है और हर कोई रास्ता तय करता है हालांकि यह गंभीर रूप से त्रुटिपूर्ण है। मैंने JavaFX में एक प्रोग्राम लिखा है ताकि उपयोगकर्ता यह जांचने की अनुमति दे सके कि क्या दो मंडल प्रत्येक सर्कल सेंटरएक्स, सेंटरवाई और रेडियस मानों को बदलकर छेड़छाड़ करते हैं और यह सूत्र बिल्कुल एक तरह से काम नहीं करता है ... मुझे पता नहीं चल सकता है कि क्यों, लेकिन जब मैं सर्कल 1 के पास सर्कल 2 ले जाएं, यह काम करता है लेकिन जब मैं सर्कल 2 के पास दूसरी ओर सर्कल 1 ले जाता हूं तो यह काम नहीं करता ..... ????? यह थोड़ी अजीब बात है ... जिस सूत्र को विपरीत तरीके से परीक्षण करने के लिए आवश्यक फॉर्मूला लगाया गया था, वैसे भी कोशिश की और यह काम नहीं करता है

if (Math.abs(circle1Radius - circle2Radius) <=
            Math.sqrt(Math.pow((circle1X - circle2X), 2)
            + Math.pow((circle1Y - circle2Y), 2)) &&
            Math.sqrt(Math.pow((circle1X - circle2X), 2)
            + Math.pow((circle1X - circle2Y), 2)) <=
            (circle1Radius + circle2Radius)} {
    return true;
} else {
    return false;
}

यह काम:

    // dx and dy are the vertical and horizontal distances
    double dx = circle2X - circle1X;
    double dy = circle2Y - circle1Y;

    // Determine the straight-line distance between centers.
    double d = Math.sqrt((dy * dy) + (dx * dx));

    // Check Intersections
    if (d > (circle1Radius + circle2Radius)) {
        // No Solution. Circles do not intersect
        return false;
    } else if (d < Math.abs(circle1Radius - circle2Radius)) {
        // No Solution. one circle is contained in the other
        return false;
    } else {
        return true;
    }

सूत्रों के लिए यहां दो सर्किलों के छेड़छाड़ के लिए जाएं

प्रयुक्त सूत्र मेरा सूत्र नहीं है, सभी क्रेडिट पॉल बोर्के (अप्रैल 1 99 7)

 First calculate the distance d between the center of the circles. d = ||P1 - P0||.

    If d > r0 + r1 then there are no solutions, the circles are separate.

    If d < |r0 - r1| then there are no solutions because one circle is contained within the other.

    If d = 0 and r0 = r1 then the circles are coincident and there are an infinite number of solutions.

Considering the two triangles P0P2P3 and P1P2P3 we can write

a2 + h2 = r02 and b2 + h2 = r12

Using d = a + b we can solve for a,

a = (r02 - r12 + d2 ) / (2 d)

It can be readily shown that this reduces to r0 when the two circles touch at one point, ie: d = r0 + r1

Solve for h by substituting a into the first equation, h2 = r02 - a2
So

P2 = P0 + a ( P1 - P0 ) / d

And finally, P3 = (x3,y3) in terms of P0 = (x0,y0), P1 = (x1,y1) and P2 = (x2,y2), is

x3 = x2 +- h ( y1 - y0 ) / d

y3 = y2 -+ h ( x1 - x0 ) / d 

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

"कम से कम अंतर" भाग लागू होता है यदि आप केवल मंडलियों के बारे में ही देखभाल करते हैं, न कि उनके आंतरिक क्षेत्रों में। यदि आप परवाह करते हैं कि सर्किल या वे क्षेत्र जो किसी भी बिंदु को साझा करते हैं , वह है - यानी, यदि एक सर्कल पूरी तरह से अन्य गिनती के अंदर आपको "छेड़छाड़" के रूप में बताती है - तो आप "कम से कम अंतर" चेक को छोड़ सकते हैं।


दो मंडल अलग-अलग होते हैं, और केवल तभी, उनके केंद्रों के बीच की दूरी योग और उनके त्रिज्या के अंतर के बीच होती है। दो सर्कल (x0, y0, R0) और (x1, y1, R1) को देखते हुए, सूत्र निम्नानुसार है:

ABS(R0 - R1) <= SQRT((x0 - x1)^2 + (y0 - y1)^2) <= (R0 + R1)

दोनों पक्षों को स्क्वायर करने से आप धीमी SQRT से बच सकते हैं, और यदि आपके इनपुट पूर्णांक हैं तो इनट्स के साथ रहें:

(R0 - R1)^2 <= (x0 - x1)^2 + (y0 - y1)^2 <= (R0 + R1)^2

चूंकि आपको केवल एक हां / नहीं परीक्षण की आवश्यकता है, इसलिए यह जांच सटीक चौराहे बिंदुओं की गणना करने से तेज़ है।

उपर्युक्त समाधान "दूसरे के अंदर एक सर्कल" मामले के लिए भी काम करना चाहिए।





circle