Hello everyone,

I found this code online that determines if two lines intersect and it also calculate the point of intersection. I have been trying to understand how it works but for the life of me I can't.

It works perfectly. but I can't understand how it works. Can someone please try and explain it?

Code is C# based

bool lines_intersect_2d(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3) 
{
    //The point of intersection if found
    Vector3 i = Vector3.Zero;

    Vector3 s1 = p1 - p0;
    Vector3 s2 = p3 - p2;

    Vector3 u = p0 - p2;

    float ip = 1f / (-s2.X * s1.Y + s1.X * s2.Y);

    float s = (-s1.Y * u.X + s1.X * u.Y) * ip;
    float t = ( s2.X * u.Y - s2.Y * u.X) * ip;

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
        if (i == Vector3.Zero) 
            i = p0 + (s1 * t);
        return true;
    }

    return false;
}

Thank you

Is this a line in 2D or 3D?

its 2D. but the guy who wrote this code is using Vector3 for some reason.

I think the best way to just use the Point class in XNA or even Vector2.

Consider all points on a lined defined as s+t*v, where s is a single point on the line, v is the direction of the line, and t is a parameter that produces points along the line. In your code, where you have two points, you can just define s=p₀ and v=p₁-p₀. If t=0, then p=p₀; if t=1, then p=p₁, and so on.

You want to find the intersection point between two line segments, which is a point common to two line segments. Thus, you have the two lines

• s₀ + t₀ * v₀, where s₀ = p₀ and v₀ = p₁-p₀ from your code, and
• s₁ + t₁ * v₁, where s₀ = p₂ and v₀ = p₃-p₂ from your code.

Find a common point along the two lines by solving for t₀ and/or t₁ from

• ?s₀ + t₀ * v₀ = s₁ + t₁ * v₁

This is a normal linear equation system, so rearrange and reformulate the problem on matrix form.

• t₀ * v₀ - t₁ * v₁ = s₁ - s₀
• [v_0, -v₁] * [t_0, t₁]^T = s₁ - s₀

Note that I assume column vectors here, and that the V-matrix is a 2-by-2 matrix where the two vectors v₀ and v₁ are the columns of the V-matrix. Finally, solve for t₀ and t₁.

• [t_0, t₁]^T = [v_0, -v₁]^-1 * (s₁ - s₀)

When you have t₀ and t₁, just plug any of them back into the corresponding lines to find the intersection point. Both of them will produce the same point.

Now that we have the theory, you can identify the maths with the code:

• My direction vectors v₀ and v₁ corresponds to your s1 and s2.
• My (s₁ - s₀) corresponds to your u, although there is a sign difference here that will be cancelled later, so no worries.
• Your ip is the determinant of my [v_0, -v₁]^-1.
• Your s and t are the x and y coordinates of the multiplication of my V-matrix and (s₁ - s₀).
• Your i being assigned inside the if-statements is when you plug one of the t's into its corresponding line equation to produce the intersection point.
• The first if-statement checks if the resulting points are outside of the two line segments bounded by the two points. That happens when t<0 or when t>1. Remove that if-statement if you want the lines to extend indefinitely.

The theory above to find the intersection point is equally valid for 3-dimensional lines as well. It will, however, find the points along the two lines that are closest to each other, and you need to find some other method to invert the V-matrix since it's no longer square; for example, the pseudo-inverse.

[...] but I can't understand how it works. Can someone please try and explain it?

The method is this: There a re 2 line segments p₀p₁ and p₂p₃ given. They can be expressed by using a ray equation (i.e. directed line) when the independent variable of the ray is restricted. In this case

r₀₁( s ) := p₀ + s * ( p₁ - p₀ ) w/ 0 <= s <= 1

r₂₃( t ) := p₂ + t * ( p₃ - p₂ ) w/ 0 <= t <= 1

In view of haegarr's post, your algorithm tries to solve the following vector equation

p0 + t*(p1-p0) = p2+s*(p3-p2)

for t and s.

Roughly speaking, the left side of this equation forms a line passing through the points p0 and p1 as independent variable t changes. In particular, for 0 <= t <= 1, it forms a section (line segment) between p0 and p1. Similarly, the right side is a line passing through the points p2 and p3 as s changes and forms a section between p2 and p3 for 0 <= s <= 1. Thus the solution of this equation should give the intersection point of these two lines.

More precisely, the algorithm solves transformed version of the above equation of the form

s*s2 - t*s1 = u,

i.e. the linear system of equations

s2.X*s - s1.X*t = u.X

s2.Y*s - s1.Y*t = u.Y,

by using Cramer's rule.

It should by mentioned, that the algorithm your presented gives only the intersection point of sections p0p1 and p2p3, not of the whole lines, since variables t and s are checked to be inside the interval [0,1]. Moreover, it does not work for "non-properly" intersecting lines.