Software & Finance

 

 







Turbo C - Finding the Intersection of two Line Segments Given End Points of Two Lines


Here is the Turbo C program for Finding the Intersection of two Line Segments Given End Points of Two Lines.

 

Find out the equation for the two lines seperately Y = MX + C

 

Where M = Slope of a Line and C = Intercept

 

To Find the slope of a line

 

slope = (y2 - y1) / (x2 - x1)

 

To Find the intercept of the line, intercept = y1 - (slope) * x1

which would be same as, intercept = y2 - (slope) * x2

 

If the difference between the slope of two lines are ZERO, then there is no intersection.

Otherwise the intersecting point is calculated using the following formula:

 

intersection_X = (c2 - c1) / (m1 - m2);

intersection_Y = m1 * intersection_X + c1;

 

Where c1 and c2 are intercepts of two lines and m1 and m2 are slope for the two lines.

 

NOTE: To find out whether the intersecting point lies on the line segment or not, we need to construct a bounding rectangle a line and check whether the point is inside the rectangle of not.

 

If you want to know just the projected lines from the either direction will meet at some point, then click here.

 


Source Code


#include <stdio.h>

#include <math.h>

 

 

int IsPointInBoundingBox(float x1, float y1, float x2, float y2, float px, float py)

{

    float left, top, right, bottom; // Bounding Box For Line Segment

    // For Bounding Box

    if(x1 < x2)

    {

        left = x1;

        right = x2;

    }

    else

    {

        left = x2;

        right = x1;

    }

    if(y1 < y2)

    {

        top = y1;

        bottom = y2;

    }

    else

    {

        top = y1;

        bottom = y2;

    }

 

    if( (px+0.01) >= left && (px-0.01) <= right && 

            (py+0.01) >= top && (py-0.01) <= bottom )

    {

        return 1;

    }

    else

        return 0;

}

 

int LineIntersection(float l1x1, float l1y1, float l1x2, float l1y2,

                            float l2x1, float l2y1, float l2x2, float l2y2,

                            float *m1, float *c1, float *m2, float *c2,

                            float* intersection_X, float* intersection_Y)

{

    float dx, dy;

 

    dx = l1x2 - l1x1;

    dy = l1y2 - l1y1;

 

    *m1 = dy / dx;

    // y = mx + c

    // intercept c = y - mx

    *c1 = l1y1 - *m1 * l1x1; // which is same as y2 - slope * x2

 

    dx = l2x2 - l2x1;

    dy = l2y2 - l2y1;

 

    *m2 = dy / dx;

    // y = mx + c

    // intercept c = y - mx

    *c2 = l2y1 - *m2 * l2x1; // which is same as y2 - slope * x2

 

    if( (*m1 - *m2) == 0)

        return 0;

    else

    {

        *intersection_X = (*c2 - *c1) / (*m1 - *m2);

        *intersection_Y = *m1 * *intersection_X + *c1;

    }

}

 

int LineSegmentIntersection(float l1x1, float l1y1, float l1x2, float l1y2,

                            float l2x1, float l2y1, float l2x2, float l2y2,

                            float *m1, float *c1, float *m2, float *c2,

                            float* intersection_X, float* intersection_Y)

{

    float dx, dy;

 

    dx = l1x2 - l1x1;

    dy = l1y2 - l1y1;

 

    *m1 = dy / dx;

    // y = mx + c

    // intercept c = y - mx

    *c1 = l1y1 - *m1 * l1x1; // which is same as y2 - slope * x2

 

    dx = l2x2 - l2x1;

    dy = l2y2 - l2y1;

 

    *m2 = dy / dx;

    // y = mx + c

    // intercept c = y - mx

    *c2 = l2y1 - *m2 * l2x1; // which is same as y2 - slope * x2

 

    if( (*m1 - *m2) == 0)

        return 0;

    else

    {

        *intersection_X = (*c2 - *c1) / (*m1 - *m2);

        *intersection_Y = *m1 * *intersection_X + *c1;

    }

    if(IsPointInBoundingBox(l1x1, l1y1, l1x2, l1y2, *intersection_X, *intersection_Y) == 1 &&

        IsPointInBoundingBox(l2x1, l2y1, l2x2, l2y2, *intersection_X, *intersection_Y) == 1)

        return 1;

    else

        return 0;

}

 

void main()

{

    float m1, c1, m2, c2;

    float l1x1, l1y1, l1x2, l1y2;

    float l2x1, l2y1, l2x2, l2y2;

    float intersection_X, intersection_Y;

    int nRet;

 

    printf("Program to find the intersection point of two line segments:\n");

 

    printf("Enter Line1 - X1: ");

    scanf("%f", &l1x1);

 

    printf("Enter Line1 - Y1: ");

    scanf("%f", &l1y1);

 

    printf("Enter Line1 - X2: ");

    scanf("%f", &l1x2);

 

    printf("Enter Line1 - Y2: ");

    scanf("%f", &l1y2);

 

    printf("Enter Line2 - X1: ");

    scanf("%f", &l2x1);

 

    printf("Enter Line2 - Y1: ");

    scanf("%f", &l2y1);

 

    printf("Enter Line2 - X2: ");

    scanf("%f", &l2x2);

 

    printf("Enter Line2 - Y2: ");

    scanf("%f", &l2y2);

 

 

    nRet = LineSegmentIntersection(l1x1, l1y1, l1x2, l1y2,

                            l2x1, l2y1, l2x2, l2y2,

                            &m1, &c1, &m2, &c2, &intersection_X, &intersection_Y);

 

    printf("Equation of line1: Y = %.2fX %c %.2f\n", m1, (c1 < 0) ? ' ' : '+',  c1);

    printf("Equation of line2: Y = %.2fX %c %.2f\n", m2, (c2 < 0) ? ' ' : '+',  c2);

 

    if(nRet == 0)

        printf("The two line segments do not intersect each other");

    else

        printf("The two line segments intersect each other at %.2f, %.2f", intersection_X, intersection_Y);

 

}

Output


 

Program to find the intersection point of two line segments:

Enter Line1 - X1: 1

Enter Line1 - Y1: 2

Enter Line1 - X2: 5

Enter Line1 - Y2: 7

Enter Line2 - X1: 3

Enter Line2 - Y1: 3

Enter Line2 - X2: 2.33

Enter Line2 - Y2: 3.66

Equation of line1: Y = 1.25X + 0.75

Equation of line2: Y = -0.99X + 5.96

The two line segments do not intersect each other

 

Press any key to continue . . .




If you have any questions, you can chat with me online through facebook by making me as your friend.


FREE Subscription: Like us on facebook to receive updates on C, C++, C#, Java, PHP, ASP.NET, XAML, WPF and Silverlight.