Determining the intersection point of the two lines is one of the fundamental problem in the computational geometry. This problem arises in various fields such as the computer graphics, robotics and geographic information systems. In this article, we will learn how to find whether two lines intersect each other or not and if they intersect, find out the point of intersection.

Lines Intersection

In 2D space, lines can be represented the mathematically as:

Ax + By + C = 0

where,

• A and B are Coefficients of x and y
• C is Constant Term.

To find their intersection, we first need to find whether the two lines ever intersect or not. We can do that using the determinant value that can be found by using the below formula:

A1 * B2 - A2 * B1

• If the result of the above equation is zero, then the lines are either parallel or incident.
• If the result is non-zero, then the line intersects.

Finding the Point of Intersection

The algorithm for finding the intersection of the two lines involves solving the system of the linear equations that represent the lines. The equations of the two lines can be represented as:

A1x +B1y + C1 = 0
A2x + B2y + C2 = 0

To find the intersection point (x, y) we need to the solve these equations as the value of x and y coordinate will be same for both equations. Refer to this article to know how to solve linear equation of two variable – Linear Equations Formula

Approach

• Calculate the determinant det using the formula.
  
• Check if the determinant is zero:
  
  • If det is zero, return 0, indicating the lines are parallel or coincident.
    
• If the determinant is not zero:
  • Calculate the intersection coordinates x and y using the formulas:
    • x = (l2->B * l1->C – l1->B * l2->C) / det
    • y = (l1->A * l2->C – l2->A * l1->C) / det

Implementation

Here is a complete C program to the find the intersection of the two lines:

// C Program to find the intersection point of two lines 
#include <stdio.h>

// Structure to represent a line
typedef struct Line {
    double A, B, C;
} line;

// Function to find the intersection point of two lines
int findIntersection(line* l1, line* l2, double* x,
                     double* y)
{
    // Calculate the determinant
    double det = l1->A * l2->B - l2->A * l1->B;

    // If the determinant is zero, the lines are parallel
    // (or coincident)
    if (det == 0) {
        return 0;
    }

    // Calculate the x and y coordinates of the intersection
    // point
    *x = (l2->B * l1->C - l1->B * l2->C) / det;
    *y = (l1->A * l2->C - l2->A * l1->C) / det;

    return 1;
}

int main()
{
    // Define two lines
    line l1 = { 1, -1, -2 };
    line l2 = { 2, -1, -3 };

    // Variables to store the intersection coordinates
    double x, y;

    // Find the intersection point of the two lines
    if (findIntersection(&l1, &l2, &x, &y)) {

        printf("Intersection point: (%.2f, %.2f)\n", x, y);
    }
    else {
        // Output if the lines are parallel (or coincident)
        printf("The lines are parallel (or coincident).\n");
    }

    return 0;
}

Intersection point: (-1.00, 1.00)

Time Complexity: O(1)
Space Complexity: O(1)

Related Article:

• Program for Point of Intersection of Two Lines
• Lines in Geometry: Definition, Types and Examples