Check if Two Line Intersect

Geeks

Description:

Line represented as two end points. Check if two lines intersect or not.

Example:

Note

Idea:

How is Orientation useful here? Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified

1. General Case: – (p1, q1, p2) and (p1, q1, q2) have different orientations and – (p2, q2, p1) and (p2, q2, q1) have different orientations.

2. Special Case – (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and – the x-projections of (p1, q1) and (p2, q2) intersect – the y-projections of (p1, q1) and (p2, q2) intersect

Code:

#include <iostream>
#include <vector>
using namespace std;

struct Point{
    int x;
    int y;
};

struct Line{
    Point p;
    Point q;
};

enum OrientationType{
    Colinear, Clockwise, ConterClockwise
};

OrientationType checkOrientation(Point p1, Point p2, Point p3){
    int flag = (p3.y - p2.y)*(p2.x-p1.x) - (p2.y-p1.y)*(p3.x-p2.x);
    if(flag==0){
        return Colinear;
    }
    else if(flag>0){
        return ConterClockwise;
    }
    else{
        return Clockwise;
    }
}

bool onSegment(Point p, Point q, Point r){
    if( (r.x<=max(p.x, q.x) && r.x>=min(p.x, q.x)) && (r.y<=max(p.y, q.y) && r.y>=min(p.y, q.y)) ) 
        return true;
    else
        return false;
}


bool lineIntersection(Line l1, Line l2){
    OrientationType o1 = checkOrientation(l1.p, l1.q, l2.p);
    OrientationType o2 = checkOrientation(l1.p, l1.q, l2.q);
    OrientationType o3 = checkOrientation(l2.p, l2.q, l1.p);
    OrientationType o4 = checkOrientation(l2.p, l2.q, l1.q);

    if( o1!=o2 && o3!=o4 ) return true;

    if(o1==0 && onSegment(l1.p, l1.q, l2.p)) return true;
    if(o2==0 && onSegment(l1.p, l1.q, l2.q)) return true;
    if(o3==0 && onSegment(l2.p, l2.q, l1.p)) return true;
    if(o4==0 && onSegment(l2.p, l2.q, l1.q)) return true;

    return false;
}

int main(){
    Point p1 = {1, 1}, q1 = {10, 1};
    Point p2 = {1, 2}, q2 = {10, 2};
    Line l1 = {p1, q1};
    Line l2 = {p2, q2};

    cout<<lineIntersection(l1, l2);
}