Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.2.
Explanation
3.
Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
C++ Code
3.4.
Python Code
3.5.
Complexity
4.
Frequently Asked Questions
4.1.
What is orientation?
4.2.
What is a line segment?
4.3.
What does it mean for two line segments to be collinear?
4.4.
What is the slope of a line segment and its formula?
4.5.
What do you mean by intersecting line segments?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if Two Line Segments Intersect

Author Malay Gain
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The problem of checking if two line segments intersect can be solved using the concept of coordinate geometry. A line segment is referred to as the portion of a line that connects two points and has a fixed length between them.

Introduction Image

Here we will use formulas that come from coordinate geometry.  

Problem Statement

For two line segments (a1,b1) and (a2,b2), check if these two intersect where a1,b1 are the endpoints of the first line segment and a2,b2 are the endpoints of the second segment.

Example

Input

a1=(1,2), b1=(1,7)  

a2=(5,5), b2=(-5,5)

Output

Yes 

Explanation

The orientation of the ordered triplet of points p,q, and r depends on the value of the below expression. 

exp = (q_y - p_y)*(r_x - q_x) - (q_x - p_x)*(r_y - q_y)   


Where p_x and p_y are 'x' and ‘y’ coordinates of point ‘p’, respectively.

Similarly, q_x and q_y are 'x' and ‘y’ coordinates of point ‘q’, respectively.

Similarly, r_x and r_y are 'x' and ‘y’ coordinates of point ‘r’, respectively.

[This relation can be proved from the slope of lines]

  • If exp=0, the orientation is collinear; 
  • If exp>0, the orientation is clockwise, and
  • If exp<0, the orientation is counterclockwise.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

To know if two line segments are intersecting or not, we need to know about the orientation of their endpoints a1, a2, b1, and b2. Here we will consider the orientation of the ordered triplet of endpoints. The orientation of the ordered triplet can be clockwise, counterclockwise, or collinear.

In general, if (a1, a2, b1), (a1, a2, b2) are two ordered triplets that have different orientations and (b1, b2, a1), (b1, b2, a2) are two ordered triplets having different orientation, two line segments will intersect.

Case 1

Orientation Case 1

  • Orientation of (a1, b1, a2) and (a1, b1, b2) are different.
  • Orientation of (a2, b2, a1) and  (a2, b2, b1) are different.
     

Case 2

Orientation Case 2

  • Orientation of (a1, b1, a2) and (a1, b1, b2) are different.
  • Orientation of (a2, b2, a1) and  (a2, b2, b1) are different.
     

Case 3

 

Orientation Case 3

  • Orientation of (a1, b1, a2) and (a1, b1, b2) are different.
  • Orientation of (a2, b2, a1) and  (a2, b2, b1) are same.
     

Case 4

Orientation Case 4

  • Orientation of (a1, b1, a2) and (a1, b1, b2) are different.
  • Orientation of (a2, b2, a1) and  (a2, b2, b1) are same.
     

Case 5

One endpoint of a line segment can lie on the other line segment. 

So, (a1,a2,b1) or (a1,a2,b2) or (b1,b2,a1) or (b1,b2,a2) can be collinear. In this case, also two line segments are intersecting. 

Algorithm

  1. Define two points in 2D space with x and y coordinates.
     
  2. The ‘dir’ function calculates the orientation of three points ‘p’, ‘q’ and ‘r’. 
    1. It returns a positive value if ‘r’ lies to the left of the line passing through ‘p’ and ‘q’ when viewed from p.
       
    2. It returns a negative value if ‘r’ lies to the right of the line passing through ‘p’ and ‘q’ when viewed from p.
       
    3. It returns 0 if all three points are collinear.
       
  3. The ‘isintersect’ function checks if the two line segments, defined by the points ‘a1’, ‘b1’, and ‘a2’, ‘b2’, intersect or not. 
    1. It first calculates the orientation of the four possible pairs of points using the dir function. 
       
    2. If the orientations of the pairs (a1,b1,a2) and (a1,b1,b2) are opposite, and the orientations of the pairs (a2,b2,a1) and (a2,b2,b1) are also opposite, then the two line segments intersect. 
       
    3. If the orientations are not opposite, or if any of the orientations is 0, then the two line segments do not intersect. 
       
  4. If ‘isintersect’ returns true, then the output gives true. Else it outputs false.

Dry Run

Let’s take the first set of points, which is a1 = {1, 2}, b1 = {1, 7}, a2 = {5, 5}, b2 = {-5,5}.

Formula taken for intersection

Use the formula of dir(p,q,r) to get the orientation of three points p, q, and r.

Intersecting lines graph

  • By using the above formula, 
    d1 = dir(a1, b1, a2) = (7 - 2) * (5 - 1) - (1 - 1) * (5 - 7) = 20
    d1 = dir(a1, b1, a2) = 20

    As d1 is positive, it means a2 lies to the left of the line passing through a1 and b1 when viewed from a1. 
     
  • By using the above formula,
    d2 = dir(a1, b1, b2) = (7 - 2) * (-5 - 1) - (1 - 1) * (5 - 7) = -30
    d2 = dir(a1, b1, b2) = -30

    As d2 is negative, it means b2 lies to the right of the line passing through a1 and b1 when viewed from a1.
     
  • By using the above formula,
    d3 = dir(a2, b2, a1) = (5 - 5) * (1 - (-5)) - (-5 - 5) * (2 - 5) = -30
    d3 = dir(a2, b2, a1) = -30 

    As d3 is negative, it means a1 lies to the right of the line passing through a2 and b2 when viewed from a2
     
  • By using the above formula,
    d4 = dir(a2, b2, b1) = (5 - 5) * (1 + 5) - (-5 - 5) * (7 - 5) = 20
    d4 = dir(a2, b2, b1) = 20

    As d1 is positive, it means b1 lies to the left of the line passing through a2 and b2 when viewed from a2.
     
  • Since d1 and d2 are opposite, and d3 and d4 are also opposite, the two line segments intersect.
     
  • Hence the output is “yes”.

C++ Code

// C++ program to check if two given line segments intersect
#include <iostream>
using namespace std;

// A struct to represent a point in 2D space
struct Point {
    int x, y;
};

/* 
   Computes the direction of the three given points
   Returns a positive value if they form a counter-clockwise orientation,
   a negative value if they form a clockwise orientation,
   and zero if they are collinear 
*/
int direction(Point p, Point q, Point r) {
    return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
}

// Checks if two line segments are collinear and overlapping
bool areCollinearAndOverlapping(Point a1, Point b1, Point a2, Point b2) {
    // Check if the line segments are collinear
    if (direction(a1, b1, a2) == 0) {
        // Check if the line segments overlap
        if (a2.x <= max(a1.x, b1.x) && a2.x >= min(a1.x, b1.x) && a2.y <= max(a1.y, b1.y) && a2.y >= min(a1.y, b1.y)) {
            return true;
        }
    }
    return false;
}

// Checks if two line segments intersect or not
bool isintersect(Point a1, Point b1, Point a2, Point b2) {
    // Compute the directions of the four line segments
    int d1 = direction(a1, b1, a2);
    int d2 = direction(a1, b1, b2);
    int d3 = direction(a2, b2, a1);
    int d4 = direction(a2, b2, b1);

    // Check if the two line segments intersect
    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
        return true;
    }

    // Check if the line segments are collinear and overlapping
    if (areCollinearAndOverlapping(a1, b1, a2, b2) || areCollinearAndOverlapping(a2, b2, a1, b1)) {
        return true;
    }

    return false;
}

int main() {
    // Define the two line segments
    Point a1 = {1, 2}, b1 = {1, 7};
    Point a2 = {5, 5}, b2 = {-5, 5};

    // Check if the two line segments intersect or not
    cout << (isintersect(a1, b1, a2, b2) ? "Yes, Line segments intersect each other" : "No, Line segments do not intersect each other") << endl;

    return 0;
}


Output

Cpp Output

Python Code

# Python program to check if two given line segments intersect

# A class to represent a point in 2D space
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

# Computes the direction of the three given points
# Returns a positive value if they form a counter-clockwise orientation,
# A negative value if they form a clockwise orientation,
# And zero if they are collinear 
def direction(p, q, r):
    return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)

# Checks if two line segments are collinear and overlapping
def areCollinearAndOverlapping(a1, b1, a2, b2):
    # Check if the line segments are collinear
    if direction(a1, b1, a2) == 0:
        # Check if the line segments overlap
        if a2.x <= max(a1.x, b1.x) and a2.x >= min(a1.x, b1.x) and a2.y <= max(a1.y, b1.y) and a2.y >= min(a1.y, b1.y):
            return True
    return False

# Checks if two line segments intersect or not
def isintersect(a1, b1, a2, b2):
    # Compute the directions of the four line segments
    d1 = direction(a1, b1, a2)
    d2 = direction(a1, b1, b2)
    d3 = direction(a2, b2, a1)
    d4 = direction(a2, b2, b1)

    # Check if the two line segments intersect
    if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
        return True

    # Check if the line segments are collinear and overlapping
    if areCollinearAndOverlapping(a1, b1, a2, b2) or areCollinearAndOverlapping(a2, b2, a1, b1):
        return True

    return False

# Define the two line segments
a1 = Point(1, 2)
b1 = Point(1, 7)
a2 = Point(5, 5)
b2 = Point(-5, 5)

# Check if the two line segments intersect or not
if isintersect(a1, b1, a2, b2):
    print("Yes, Line segments intersect each other")
else:
    print("No, Line segments do not intersect each other")


Output

Python Output

Complexity

Time complexity

The time complexity of the ‘isIntersect()’ function is O(1) because it always performs a fixed number of arithmetic operations and comparisons regardless of the input size.

Space complexity

The space complexity is O(1) because it only uses a constant amount of memory to store the input points and intermediate variables.

Frequently Asked Questions

What is orientation?

The orientation of a line segment refers to the direction in which the line segment extends.

What is a line segment?

A segment of a line connecting two given points is known as a line segment.

What does it mean for two line segments to be collinear?

It means that the line segments lie on the same straight line.

What is the slope of a line segment and its formula?

For a line segment connecting two points (x1,y1) and (x2,y2), Slope =(y2 - y1) / (x2 - x1)

What do you mean by intersecting line segments?

It means that two or more line segments share a common point.

Conclusion

In this blog, we learned how to check if two line segments intersect. We have implemented the problem in C++ and Python programming languages.

For more similar articles, you can refer following links:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Convex Hull Problem using Divide and Conquer Algorithm
Next article
Find Maximum Perimeter of Quadrilateral Formed by Choosing Sides from Given Array.
Live masterclass