Find point of 2D Line Intersection
Get this book > Problems on Array: For Interviews and Competitive Programming
Reading time: 40 minutes  Coding time: 5 minutes
Line Intersection coordinates are the solution of two corresponding lines taken into consideration in the 2Dimensional plane. We will cover two algorithms namely:
 Elimination Method (Method 1)
 Determinant Method (Method 2)
Both methods take constant time O(1) assuming the multiplication takes O(1) time.
Flowchart
Following flowchart explains the overall process:
Pseudocode of Elimination Method :
 Step 1 : Input four coordinates of two lines.
 Step 2 : Compute both the equations in form of ax + by + c = d.
 Step 3 : Before finding the intersection point coordinate, check whether the lines are parallel or not from the values of slope of each line.
 Step 4 : To find the values of intersection point, xcoordinate and ycoordinate, eliminate xcoefficient by making it equal in units in both the equations, which would lead to get the value of y coordinate of intersection point.
 Step 5 : Similarly, to compute xcoordinate eliminate the ycoefficient from both the equations by making their coefficients equal in units which again leads to obtain the xcoordinate of intersection point.
Algorithm of Elimination Method

step 1 : Accept the two end coordinates of each for two line segments
for line1 : (X_{1}, Y_{1}) & (X_{2}, Y_{2})
for line2 : (X_{3}, Y_{3}) & (X_{4}, Y_{4}) 
step 2 : Let the equations of lines by two point form be :
Eq1 : a_{1}x + b_{1}y = c_{1};
Eq2 : a_{2}x + b_{2}y = c_{2};
solving the above equation simultaneously by eliminating the x variable by making its coefficients equal by multipliying Eq1 by a_{2} and Eq2 by a_{1} and further substracting Eq2 from Eq1. 
step 3 : We will get following Equations,
Eq1.1 : a_{2}a_{1}x + a_{2}b_{1}y = a_{2}c_{1};
Eq2.1 : a_{1}a_{2}x + a_{1}b_{2}y = a_{1}c_{2};
substracting Eq2.1 from Eq1.1. 
step 4 : After substracting Eq2.1 from Eq1.1 we get,
the value of ycoordinate of intersection point
y = a_{1}c_{2}  a_{2}c_{1} / (a_{1}b_{2}  a_{2}b_{1}) 
step 5 : To compute the value of xcoordinate, similar above process has to be carried out.
Example solved by Elimination Method
 step 1 : following are the coordinates of two lines :
Line1 : (1, 6) & (2, 5)
Line2 : (1/3, 8) & (2/3, 7)
 step 2 : Form the equations
Equation of Line1 : x + y = 7,
Equation of Line2 : 3x + y = 9
 step 3 : Check whether Line1 and Line2 are parallel or not.
slope of Line1 = (5  6)/(2  1)
= 1
slope of Line2 = (7  8)/(2/3  1/3)
= 3
Here slope of Line1 an Line2 are unequal hence they are not parallel.
 step 4 : solving for intersection of Line1 and Line2 for x coordinate,
as here coefficient of y is already same of both the lines, substracting Line2 from Line1 we get,
* 3x  x = 9  7
* 2x = 2
* x = 1
substituting x = 1 in Line 1 we get value of y = 6.
 step 5 : Hence intersection of Line1 and Line2 is (1, 6)
Implementation of Elimination Method
#include <iostream>
#include <vector>
class EliminationMethd2DLineIntersection
{
public:
void acceptTheCoordinates(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4);
void intersection1(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4);
private:
std::vector<double> a, b, c, d; //four coordinates constituting 2 Dimensional Lines.
};
void EliminationMethd2DLineIntersection::acceptTheCoordinates(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
{
a.push_back(x1);
a.push_back(y1);
b.push_back(x1);
b.push_back(y1);
c.push_back(x1);
c.push_back(y1);
d.push_back(x1);
d.push_back(y1);
intersection1(a[0], a[1], b[0], b[1], c[0], c[1], d[0], d[1]);
}
void EliminationMethd2DLineIntersection::intersection1(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
{
double x12 = x1  x2;
double x34 = x3  x4;
double y12 = y1  y2;
double y34 = y3  y4;
double c = x12 * y34  y12 * x34;
double a = x1 * y2  y1 * x2;
double b = x3 * y4  y3 * x4;
if(c != 0)
{
double x = (a * x34  b * x12) / c;
double y = (a * y34  b * y12) / c;
std::cout << "Intersection point coordinates : \n";
std::cout << "Xin : " << x << std::endl;
std::cout << "Yin : " << y << std::endl;
}
else
{
std::cout << "Lines are parallel";
}
}
int main()
{
EliminationMethd2DLineIntersection obj;
int value;
double x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6, x7, y7, x8, y8;
std::cout << "\nEnter the Coordinates for Line1";
std::cout << "\nEnter the Xcoordinate for Point1: ";
std::cin >> x1;
std::cout << "\nEnter the Ycoordinate for Point1: ";
std::cin >> y1;
std::cout << "\nEnter the Xcoordinate for Point2: ";
std::cin >> x2;
std::cout << "\nEnter the Ycoordinate for Point2: ";
std::cin >> y2;
std::cout << "\nEnter the Coordinates for Line2";
std::cout << "\nEnter the Xcoordinate for Point1: ";
std::cin >> x3;
std::cout << "\nEnter the Ycoordinate for Point1: ";
std::cin >> y3;
std::cout << "\nEnter the Xcoordinate for Point2: ";
std::cin >> x4;
std::cout << "\nEnter the Ycoordinate for Point2: ";
std::cin >> y4;
obj.acceptTheCoordinates(x1,y1, x2, y2, x3, y3, x4, y4);
return 0;
}
Input:
Enter the Coordinates for Line1
Enter the Xcoordinate for Point1: 0
Enter the Ycoordinate for Point1: 0
Enter the Xcoordinate for Point2: 1
Enter the Ycoordinate for Point2: 2
Enter the Coordinates for Line2
Enter the Xcoordinate for Point1: 0
Enter the Ycoordinate for Point1: 6
Enter the Xcoordinate for Point2: 1
Enter the Ycoordinate for Point2: 5
Output:
Intersection point coordinates :
Xin : 2
Yin : 4
Determinant Method
Now, we will explore the second approach of finding the intersection of two points using Determinant Method.
Pseudocode of Determinant Method
 Step 1 : Input four coordinates of two lines.
 Step 2 : Compute both the equations in form of ax + by + c = d.
 Step 3 : Before finding the intersection point coordinate, check whether the lines are parallel or not by ensuring if determinant is zero lines are parallel.
 Step 4 : To find the values of intersection point, xcoordinate and ycoordinate, apply the formulas mentioned in the figure given below.
 Step 4.1 : The formulas given in figure below are calculated by using technique known elimination, where to compute xcoordinate of intersection we have to eliminate ycoordinate from both the equations we have build in Step 2 so far by, making the coefficients equal of ycoordinate in both the equations. Similarly formula for ycoordinate of intersection is computed by eliminating xcoordinating making xcoordinate coefficients equal in both the equations.
Algorithm of Determinant Method
Following is the computation to calculate the x and y coordinate of intersection point by Determinant Method.

step 1 : Equation of Lines by two point form is given by in ax + by + c = 0,
Eq 1 : (y_{2}  y_{1})x  (x_{2}  x_{1})y = x_{1}y_{2}  x_{2}y_{1}
Eq 2 : (y_{4}  y_{3})x  (x_{4}  x_{3})y = x_{3}y_{4}  x_{4}y_{3}By using cramer's rule on above equation we get,

step 2 : Intersection coordinates :
Explaning cramer's rule in solving above Eq 1 and Eq 2 
step 2.1 : Solving Eq 1 and Eq 2 for y value, multiply Eq 1 by (y_{4}  y_{3}) and multiply Eq 2 by (y_{2}  y_{1}).

step 2.2 : After following step 2.1 we get,
Eq 1.1 : (y_{4}  y_{3}) (y_{2}  y_{1})x  (y_{4}  y_{3}) (x_{2}  x_{1}) y = (y_{4}  y_{3}) (x_{1}y_{2}  x_{2}y_{1})
Eq 2.2 : (y_{2}  y_{1}) (y_{4}y_{3}) x  (y_{2}  y_{1}) (x_{4}  x_{3}) y = (y_{2}  y_{1}) (x_{3}y_{4}  x_{4}y_{3}) 
step 2.3 : Substracting Eq 2.2 from Eq 1.1 we get,
y = (y_{4}  y_{3}) (x_{1}y_{2}  x_{2}y_{1})  (y_{2}  y_{1}) (x_{3}y_{4}  x_{4}y_{3}) / ((y_{4}  y_{3}) (x_{2}  x_{1})  (y_{2}  y_{1}) (x_{4}  x_{3})) 
step 2.5 : similarly value for x coordinate would be calculated.
Example solved by Determinant Method
step 1 : Following are the coordinates of :
Line 1 : (1, 4) & (2, 5)
Line 2 : (1, 10) & (0, 12)
step 2 : Computing Equations of above lines are:
Line 1 : x  y + 3 = 0
Line 2 : 2x + y  12 = 0
step 3 : Computing determinant to check whether lines are parallel or not.
determinant = (1) * (1)  (1) * (2)
* = 1 + 2
* = 3
where determinant is nonzero meaning lines are not parallel.
step 4 : By applying the formulae for x and y coordinates given above in figure in method2 algorithm, the intersection point (xin, yin) = (3, 6)
Implementation of Determinant Method
#include <iostream>
class TwoDimensionalLineIntersection
{
public:
bool determinantMethod();
void setCoordinatesOfLines(double x1_, double y1_, double x2_, double y2_, double x3_, double y3_, double x4_, double y4_);
void printIntersectionPoints();
private:
double x1_, y1_, x2_, y2_, x3_, y3_, x4_, y4_, xin_, yin_;
};
void TwoDimensionalLineIntersection :: setCoordinatesOfLines(double x1_, double y1_, double x2_, double y2_, double x3_, double y3_, double x4_, double y4_)
{
this>x1_ = x1_;
this>x2_ = x2_;
this>x3_ = x3_;
this>x4_ = x4_;
this>y1_ = y1_;
this>y2_ = y2_;
this>y3_ = y3_;
this>y4_ = y4_;
}
bool TwoDimensionalLineIntersection :: determinantMethod()
{
double slopeOfLine1;
double slopeOfLine2;
if(x2_  x1_ != 0)
slopeOfLine1 = (y2_  y1_)/(x2_  x1_);
else
slopeOfLine1 = 0;
if(x4_  x3_ != 0)
slopeOfLine2 = (y4_  y3_)/(x4_  x3_);
else
slopeOfLine1 = 0;
if(slopeOfLine1 != slopeOfLine2)
{
xin_ = ((x1_*y2_  y1_*x2_)*(x3_  x4_)  (x3_*y4_  y3_*x4_)*(x1_  x2_) )/( ((x1_  x2_)*(y3_  y4_)) ((y1_  y2_)*(x3_  x4_)));
yin_ = ((x1_*y2_  y1_*x2_)*(y3_  y4_)  (x3_*y4_  y3_*x4_)*(y1_  y2_) )/( ((x1_  x2_)*(y3_  y4_)) ((y1_  y2_)*(x3_  x4_)));
return true;
}
else
return false;
}
void TwoDimensionalLineIntersection ::printIntersectionPoints()
{
if(determinantMethod())
{
std::cout << "\nIntersection Coordinate : ";
std::cout << "\nXcoordinate : " << xin_;
std::cout << "\nYcoordinate : " << yin_;
} else
std::cout << "\nLines are Parallel.";
}
int main()
{
TwoDimensionalLineIntersection t;
double x1, y1, x2, y2, x3, y3, x4, y4;
std::cout << "\nEnter the Coordinates for Line1 : ";
std::cout << "\nLine1  x1coordinate : ";
std::cin >> x1;
std::cout << "\nLine1  y1coordinate : ";
std::cin >> y1;
std::cout << "\nLine1  x2coordinate : ";
std::cin >> x2;
std::cout << "\nLine1  y2coordinate : ";
std::cin >> y2;
std::cout << "\nEnter the Coordinates for Line2 : ";
std::cout << "\nLine2  x3coordinate : ";
std::cin >> x3;
std::cout << "\nLine2  y3coordinate : ";
std::cin >> y3;
std::cout << "\nLine2  x4coordinate : ";
std::cin >> x4;
std::cout << "\nLine2  y4coordinate : ";
std::cin >> y4;
t.setCoordinatesOfLines(x1, y1, x2, y2, x3, y3, x4, y4);
t.printIntersectionPoints();
}
Input:
Enter the Coordinates for Line1 :
Line1  x1coordinate : 0
Line1  y1coordinate : 0
Line1  x2coordinate : 1
Line1  y2coordinate : 2
Enter the Coordinates for Line2 :
Line2  x3coordinate : 0
Line2  y3coordinate : 6
Line2  x4coordinate : 1
Line2  y4coordinate : 5
Output:
Intersection Coordinate :
Xcoordinate : 2
Ycoordinate : 4
Complexity
The time and space complexity of finding Intersection point of 2D Lines by Determinant Method are:
 Worst case time complexity:
Î˜(1)
 Average case time complexity:
Î˜(1)
 Best case time complexity:
Î˜(1)
 Space complexity:
Î˜(1)