Why is this line intersection code not working?

Question

I have the following code to determine the intersection of two 2D lines. It's not working and I'm not sure why; I've been copying code from multiple sources without much change.

The lines extend infinitely from a given midpoint. The "vector()" referenced in the below code is a 2D vector of magnitude 1.0 that indicates the direction in which the line extends (the line also extends in the negative direction, it's not a ray).

Earlier, I was using this method for determining the intersection: Intersection point of two lines (2 dimensions)

After that gave me wrong results, I went with the method on Wikipedia.

float x1 = line1.location().x();
float y1 = line1.location().y();
float x2 = x1 + line1.vector().x();
float y2 = y1 + line1.vector().y();

float x3 = line2.location().x();
float y3 = line2.location().y();
float x4 = x3 + line2.vector().x();
float y4 = y3 + line2.vector().y();

float d = ((x1 - x2) * (y3 - y4)) - ((y1 - y2) * (x3 - x4));
if(d == 0) // If parallel, defaults to the average location of the lines.
    return new Vector2f((x1 + x3) * 0.5f, (y1 + y3) * 0.5f);
else
{
    float a = (x1 * y2) - (y1 * x2);
    float b = (x3 * y4) - (y3 * x4);
    return new Vector2f(((a * (x3 - x4)) - ((x1 - x2) * b)) / d, 
                        ((a * (y3 - y4)) - ((y1 - y2) * b)) / d);
}

Two examples of how it is wrong (The orange dot is the returned point of intersection):q

Ex 1 Ex 2

It returns a point along the primary line, but it doesn't return a point on the second. the same bugs happen in both methods, so I'm really not sure what I'm doing wrong.

How can I fix this?

EDIT: Actually, this code works fine; my visualization code had an error.

dhuckle3 dhuckle3 · Accepted Answer · 2012-03-15T16:18:30

I believe you've confused what the location() and vector() methods return. Unless i'm mistaken the location().x() gives you a point on the line created by the vector while vector().x() gives you the magnitude of the x value of the vector. (e.g. a horizontal has a vector().y() of 0)

You are adding the magnitude of the vector to the starting point. Instead try multiplying the starting point by the magnitude

float x2 = x1 * line1.vector().x();
float y2 = y1 * line1.vector().y();

Why is this line intersection code not working?

2 Answers