mathgeometryglslshaderline-intersection

How to calculate the intersection point between an infinite line and a line segment?


Basically, a function that fulfills this signature:

function getLineIntersection(vec2 p0, vec2 direction, vec2 p2, vec2 p3) {
   // return a vec2
}

I have looked around at existing solutions, and they all seem to deal with how to find the intersection between two line segments, or between two infinite lines. Is there a solution for this problem where the line has an initial position, an angle, and needs to determine if it intersects with a line segment? Basically, something like this:

enter image description here

There should be one line segment that starts in a location and has a unit direction, and another line segment that is just a line connected by two points. Is this possible, and if so, is there a good way of calculating the intersection point, if it exists?


Solution

  • If you've a endless line which is defined by a point P and a normalized direction R and a second endless line, which is defined by a point Q and a direction S, then the intersection point of the endless lines X is:

    alpha ... angle between Q-P and R
    beta  ... angle between R and S
    
    gamma  =  180° - alpha - beta
    
    h  =  | Q - P | * sin(alpha)
    u  =  h / sin(beta)
    
    t  = | Q - P | * sin(gamma) / sin(beta)
    
    t  =  dot(Q-P, (S.y, -S.x)) / dot(R, (S.y, -S.x))  =  determinant(mat2(Q-P, S)) / determinant(mat2(R, S))
    u  =  dot(Q-P, (R.y, -R.x)) / dot(R, (S.y, -S.x))  =  determinant(mat2(Q-P, R)) / determinant(mat2(R, S))
    
    X  =  P + R * t  =  Q + S * u
    

    If you want to detect if the intersection is on the lien, you need to compare the distance of the intersection point with the length of the line.
    The intersection point (X) is on the line segment if t is in [0.0, 1.0] for X = p2 + (p3 - p2) * t

    vec2 getLineIntersection(vec2 p0, vec2 direction, vec2 p2, vec2 p3) 
    {
        vec2 P = p2;
        vec2 R = p3 - p2;  
        vec2 Q = p0;
        vec2 S = direction;
    
        vec2 N = vec2(S.y, -S.x);
        float t = dot(Q-P, N) / dot(R, N);
    
        if (t >= 0.0 && t <= 1.0)
            return P + R * t;
    
        return vec2(-1.0);
    }