CODEWITHSUNDEEP
mathgeometryglslshaderline-intersection
Ryan Peschel
Ryan Peschel

Reputation: 11808

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?

Upvotes: 3

Views: 1209

Answers (2)

Rabbid76
Rabbid76

Reputation: 210998

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);
}

Upvotes: 2

jcerveny
jcerveny

Reputation: 350

Start with the intersection of two infinite lines, expressed in parametric form (e.g., A + tp, where A is the "start point", p is the direction vector and t is a scalar parameter). Solve a system of two equations to get the two parameters of the intersection point.

Now if one of your lines is really a segment AB, and B = A + p (i.e., the direction vector goes from A to B), then if the parameter t is between 0 and 1, the intersection lies on the segment.

Upvotes: 1

Related Questions