सी ++ प्रक्रिया निर्धारित करने के लिए कि क्या दो खंड छेड़छाड़ करते हैं

Question

मैं हाल ही में कम्प्यूटेशनल ज्यामिति के साथ थोड़ा सा काम कर रहा हूं, और मैं यह जांचने का एक तरीका ढूंढने की कोशिश कर रहा हूं कि दो रेखा खंड अलग-अलग हैं या नहीं। मैंने सोचा कि मैं इसे निर्धारित करने के लिए काउंटरक्लॉक दिशा (शॉर्ट के लिए सीसीडब्ल्यू) का उपयोग कर सकता हूं। यहाँ मेरी कोड अब तक है:

struct point { double x, y }; 

double CCW(point a, point b, point c) 
{ return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); } 

int intersect(point a, point b, point c, point d) 
{ return (CCW(a,b,c)*CCW(a,b,d)<0 && CCW(c,d,b)*CCW(c,d,a)<0); } 

ऊपर कोड परीक्षण मामलों मैंने प्रवेश किया के लिए काम किया है, और यह बहुत पठनीय और लागू करने के लिए बहुत आसान है। लेकिन वेब पर खोज करने के बाद, मुझे सेगमेंट चौराहे की समस्या को हल करने का एक और तरीका मिला। कोड मेरा जैसा है, लेकिन इसमें कुछ और if बयान हैं जो मेरा कार्यान्वयन छोड़ देता है। यहां कोड है:

struct line { point s, e; }; 

int middle(int a, int b, int c) { 
    int t;  
    if (a > b) { 
    t = a; 
    a = b; 
    b = t; 
    } 
    if (a <= c && c <= b) return 1; 
    return 0; 
} 

int intersect(line a, line b) { 
    if ((CCW(a.s, a.e, b.s) * CCW(a.s, a.e, b.e) < 0) && 
    (CCW(b.s, b.e, a.s) * CCW(b.s, b.e, a.e) < 0)) return 1; 

    if (CCW(a.s, a.e, b.s) == 0 && middle(a.s.x, a.e.x, b.s.x) && middle(a.s.y, a.e.y, b.s.y)) return 1; 
    if (CCW(a.s, a.e, b.e) == 0 && middle(a.s.x, a.e.x, b.e.x) && middle(a.s.y, a.e.y, b.e.y)) return 1; 
    if (CCW(b.s, b.e, a.s) == 0 && middle(b.s.x, b.e.x, a.s.x) && middle(b.s.y, b.e.y, a.s.y)) return 1; 
    if (CCW(b.s, b.e, a.e) == 0 && middle(b.s.x, b.e.x, a.e.x) && middle(b.s.y, b.e.y, a.e.y)) return 1; 

    return 0; 
} 

क्या कोई बता सकता है कि दो कार्यान्वयन के बीच क्या अंतर है, और कौन सा सुरक्षित है? अग्रिम में धन्यवाद।

Answer 1

जो फ़ंक्शन आपको मिला वह उस मामले की जांच भी कर रहा है जहां रेखा खंड एक ही पंक्ति में स्थित हैं। उस स्थिति में, यह पता लगाने की एक-आयामी समस्या बन जाती है कि क्या दो पंक्ति खंड ओवरलैप हैं। आपका कोड इस मामले में झूठी वापसी करेगा। चाहे यह पसंद किया गया हो या नहीं, आवेदन पर निर्भर करता है।

उदाहरण:

point a={1,0}, b={3,0}, c={2,0}, d={4,0}; 

intersect(a,b,c,d); // your function will return false, 
        // but the one you found will return true 

समारोह आप पाया भी मामलों को देखता है, जहां एक लाइन खंड के अंतिम बिंदु अन्य रेखा खंड के साथ निहित है:

उदाहरण:

point a={1,0}, b={3,0}, c={2,0}, d={2,3}; 

intersect(a,b,c,d); // your function will return false, 
        // but the one you found will return true