जांचें कि दो रेखा खंड प्रतिच्छेद करते हैं या नहीं

परिचय

दो रेखा-खंड दिए गए हैं। पहली रेखा खंड से बिंदु p1, p2 और दूसरी रेखा खंड से q1, q2। हमें जांचना है कि दोनों रेखा खंड प्रतिच्छेद कर रहे हैं या नहीं।

हम कह सकते हैं कि दोनों रेखा खंड प्रतिच्छेद कर रहे हैं जब ये शर्तें पूरी होती हैं:

• जब (p1, p2, q1) और (p1, p2, q2) का अभिविन्यास अलग हो और
• (q1, q2, p1) और (q1, q2, p2) का अभिविन्यास अलग हो।

एक और शर्त है जब (p1, p2, q1), (p1, p2, q2), (q1, q2, p1), (q1, q2, p2) संरेखी (collinear) हों।

इनपुट और आउटपुट

इनपुट: दो रेखा-खंडों के बिंदु
रेखा-खंड 1: (0, 0) से (5, 5)
रेखा-खंड 2: (2, -10) से (3, 10)
आउटपुट: रेखाएं प्रतिच्छेद कर रही हैं

एल्गोरिदम

direction(a, b, c)

इनपुट: तीन बिंदु।

आउटपुट: जांचें कि वे संरेखी हैं या वामावर्त या दक्षिणावर्त दिशा में हैं।

Begin
    val := (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y)
    यदि val = 0, तो
        संरेखी लौटाएं
    अन्यथा यदि val < 0, तो
        वामावर्त लौटाएं
    दक्षिणावर्त लौटाएं
End

isIntersect(l1, l2)

इनपुट: दो रेखा खंड, प्रत्येक रेखा के दो बिंदु p1 और p2 हैं।

आउटपुट: सत्य, जब वे प्रतिच्छेद कर रहे हों।

Begin
    dir1 = direction(l1.p1, l1.p2, l2.p1);
    dir2 = direction(l1.p1, l1.p2, l2.p2);
    dir3 = direction(l2.p1, l2.p2, l1.p1);
    dir4 = direction(l2.p1, l2.p2, l1.p2);
    यदि dir1 ≠ dir2 और dir3 ≠ dir4, तो
        सत्य लौटाएं
    यदि dir1 = 0 और l2.p1 रेखा l1 पर है, तो
        सत्य लौटाएं
    यदि dir2 = 0 और l2.p2 रेखा l1 पर है, तो
        सत्य लौटाएं
    यदि dir3 = 0 और l1.p1 रेखा l2 पर है, तो
        सत्य लौटाएं
    यदि dir4 = 0 और l1.p2 रेखा l2 पर है, तो
        सत्य लौटाएं
    असत्य लौटाएं
End

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

struct Point {
    int x, y;
};

struct line {
    Point p1, p2;
};

bool onLine(line l1, Point p) {
    // जांचें कि p रेखा पर है या नहीं
    if (p.x <= max(l1.p1.x, l1.p2.x) && p.x >= min(l1.p1.x, l1.p2.x) &&
        (p.y <= max(l1.p1.y, l1.p2.y) && p.y >= min(l1.p1.y, l1.p2.y)))
        return true;
    return false;
}

int direction(Point a, Point b, Point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0; // संरेखी
    else if (val < 0)
        return 2; // वामावर्त दिशा
    return 1; // दक्षिणावर्त दिशा
}

bool isIntersect(line l1, line l2) {
    // दो रेखाओं और दूसरी रेखा के बिंदुओं के लिए चार दिशा
    int dir1 = direction(l1.p1, l1.p2, l2.p1);
    int dir2 = direction(l1.p1, l1.p2, l2.p2);
    int dir3 = direction(l2.p1, l2.p2, l1.p1);
    int dir4 = direction(l2.p1, l2.p2, l1.p2);
    
    if (dir1 != dir2 && dir3 != dir4)
        return true; // वे प्रतिच्छेद कर रहे हैं
    if (dir1==0 && onLine(l1, l2.p1)) // जब रेखा2 के p2 रेखा1 पर हैं
        return true;
    if (dir2==0 && onLine(l1, l2.p2)) // जब रेखा2 के p1 रेखा1 पर हैं
        return true;
    if (dir3==0 && onLine(l2, l1.p1)) // जब रेखा1 के p2 रेखा2 पर हैं
        return true;
    if (dir4==0 && onLine(l2, l1.p2)) // जब रेखा1 के p1 रेखा2 पर हैं
        return true;
    return false;
}

int main() {
    line l1 = {{0,0}, {5, 5}};
    line l2 = {{2,-10}, {3, 10}};
    if (isIntersect(l1, l2))
        cout << "Lines are intersecting";
    else
        cout << "Lines are not intersecting";
}

आउटपुट

Lines are intersecting