Do you think IIT Guwahati certified course can help you in your career?
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.
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.
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.
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 of (a1, b1, a2) and (a1, b1, b2) are different.
Orientation of (a2, b2, a1) and (a2, b2, b1) are different.
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 of (a1, b1, a2) and (a1, b1, b2) are different.
Orientation of (a2, b2, a1) and (a2, b2, b1) are same.
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
Define two points in 2D space with x and y coordinates.
The ‘dir’ function calculates the orientation of three points ‘p’, ‘q’ and ‘r’.
It returns a positive value if ‘r’ lies to the left of the line passing through ‘p’ and ‘q’ when viewed from p.
It returns a negative value if ‘r’ lies to the right of the line passing through ‘p’ and ‘q’ when viewed from p.
It returns 0 if all three points are collinear.
The ‘isintersect’ function checks if the two line segments, defined by the points ‘a1’, ‘b1’, and ‘a2’, ‘b2’, intersect or not.
It first calculates the orientation of the four possible pairs of points using the dir function.
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.
If the orientations are not opposite, or if any of the orientations is 0, then the two line segments do not intersect.
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}.
Use the formula of dir(p,q,r) to get the orientation of three points p, q, and r.
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;
}
You can also try this code with Online C++ Compiler
# 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")
You can also try this code with Online Python Compiler
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:
310+ registered 
