Check if two line segments intersect

Let two line-segments are given. The points p1, p2 from the first line segment and q1, q2 from the second line segment. We have to check whether both line segments are intersecting or not.

We can say that both line segments are intersecting when these cases are satisfied:

• When (p1, p2, q1) and (p1, p2, q2) have a different orientation and
• (q1, q2, p1) and (q1, q2, p2) have a different orientation.

There is another condition is when (p1, p2, q1), (p1, p2, q2), (q1, q2, p1), (q1, q2, p2) are collinear.

Input and Output

Input: Points of two line-segments Line-segment 1: (0, 0) to (5, 5) Line-segment 2: (2, -10) to (3, 10) Output: Lines are intersecting

Algorithm

direction(a, b, c)

Input: Three points.

Output: Check whether they are collinear or anti-clockwise or clockwise direction.

Begin    val := (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y)    if val = 0, then       return collinear    else if val < 0, then       return anti-clockwise    return clockwise End

isIntersect(l1, l2)

Input: Two line segments, each line has two points p1 and p2.

Output: True, when they are intersecting.

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);    if dir1 ≠ dir2 and dir3 ≠ dir4, then       return true    if dir1 =0 and l2.p1 on the line l1, then       return true    if dir2 = 0 and l2.p2 on the line l1, then       return true    if dir3 = 0 and l1.p1 on the line l2, then       return true    if dir4 = 0 and l1.p2 on the line l2, then       return true    return false End

Example

#include<iostream> using namespace std; struct Point {    int x, y; }; struct line {    Point p1, p2; }; bool onLine(line l1, Point p) {   //check whether p is on the line or not    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;     //colinear    else if(val < 0)       return 2;    //anti-clockwise direction       return 1;    //clockwise direction } bool isIntersect(line l1, line l2) {    //four direction for two lines and points of other line    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; //they are intersecting    if(dir1==0 && onLine(l1, l2.p1)) //when p2 of line2 are on the line1       return true;    if(dir2==0 && onLine(l1, l2.p2)) //when p1 of line2 are on the line1       return true;    if(dir3==0 && onLine(l2, l1.p1)) //when p2 of line1 are on the line2       return true;    if(dir4==0 && onLine(l2, l1.p2)) //when p1 of line1 are on the line2       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"; }

Output

Lines are intersecting