Finding the intersection point of two lines (and line segments)

Introduction

Quite often, when developing games, it becomes necessary to find the intersection point of straight lines, segments, rays, etc. How to implement this in the simplest possible way, in this article.

Popular methods and their criticism

Perhaps many will remember a way from school algebra - to make equations of two straight lines, equate their right-hand sides, find x, and substitute it into the equation of a straight line to find y ( More details here ).



However, this method becomes quite cumbersome when writing code (perhaps this is why you are reading this article now), moreover, it is not universal: if one of the straight lines is parallel to the Y axis, we will get a division by zero error when calculating the slope, and we have to register a code for this case; if two lines are parallel, you need to tinker with the processing of this case too. This code becomes long and ugly.



In search of a more elegant solution to this problem, I stumbled upon some very interesting ways based on vector multiplication (habr.com/ru/post/267037 ) and ray castinging ( ru.wikipedia.org/wiki/Ray_casting#Concept ). But in my opinion, they are unnecessarily complex computationally. Therefore, I present to your attention (and criticism) my method.

My way

Task

The coordinates of two segments are given. You need to find out if the segments intersect, and if so, at what point. For this purpose, we will write a function.

Decision

Legend for avoiding misunderstandings: a - vector a, a (y) - projection of vector a onto the Y axis, a {x1, y1} - vector a, specified by coordinates x1, y1.



Let's represent our segments in the form of two vectors: a {x2-x1; y2-y1} and b {x3-x4; y3-x4}. Note that vector b is in the opposite direction from what is expected. Let's introduce a vector c {x3-x1; y3-y1}. Note that a * k + b * n = c, where k, n are some coefficients. Thus, we obtain a system of equations:



a (x) * k + b (x) * n = c (x)

a (y) * k + b (y) * n = c (y)

Our task is reduced to finding these coefficients (to tell the truth, it is enough to find only one of them).



I propose to multiply both sides of the lower equation by q = -a (x) / a (y). So after adding two equations, we immediately get rid of k. Finding n is reduced to solving an ordinary linear equation. It is important to note that n may not have a solution.



The attentive reader will notice that when a (y) = 0, we get an error. Let's write the branching at the stage of finding a (y). This case is even simpler, because we immediately get an equation with one unknown.



I recommend trying to output n yourself, so it will be clearer what comes from in the code below.



Knowing n, you can find the intersection point, for this we subtract the vector b * n from the coordinate of the point (x3, y3)

Putting it together

float dot[2];  //  

bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
    float n;
    if (y2 - y1 != 0) {  // a(y)
        float q = (x2 - x1) / (y1 - y2);   
        float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; }  // c(x) + c(y)*q
        float fn = (x3 - x1) + (y3 - y1) * q;   // b(x) + b(y)*q
        n = fn / sn;
    }
    else {
        if (!(y3 - y4)) { return 0; }  // b(y)
        n = (y3 - y1) / (y3 - y4);   // c(y)/b(y)
    }
    dot[0] = x3 + (x4 - x3) * n;  // x3 + (-b(x))*n
    dot[1] = y3 + (y4 - y3) * n;  // y3 +(-b(y))*n
    return 1;
}

This function takes the coordinates of the vertices and returns the value 1 if the straight lines of the segments (namely, the straight lines) intersect, otherwise 0. If you need the coordinates of the vertices, you can take them from the dot [] array.



Important: when you enter two coincident lines, the algorithm displays no intersection. The algorithm finds the intersection point of the lines on which the line segments lie, so the point may be outside the segment (which you will have to check in your code).



Let's apply the function:

int main() {
    if (cross(1,1,7,2, 7,3,5,6)) {
        std::cout << dot[0] << " " << dot[1] << std::endl;
    }
    else {
        std::cout<<"Not cross!"<<std::endl;
    }
    return 0;
}

Afterword

Although I did not come across this method in the process of googling my problem and developed the algorithm myself, I do not pretend to be completely original (and correct). So welcome to the comments!