2D Line Line intersection function not working

Question

I have a 2D line-line intersection function (infinite lines). Each line is defined by 2 points and are interpreted as infinite lines not line segments.

But it doesn't seem to find the correct intersection point. Not sure where i am going wrong, i interpreted the math from the Wikipedia.

My function:

//https://en.m.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line
public static bool LineLineIntersectionInfinite(Vector2 line1Point1, Vector2 line1Point2, Vector2 line2Point1, Vector2 line2Point2, out Vector2 intersectionPoint)
{
    // define the out parameter
    intersectionPoint = Vector2.zero;

    //1 = line1Point1
    //2 = line1Point2
    //3 = line2Point1
    //4 = line2Point2

    var x1 = line1Point1.x;
    var x2 = line1Point2.x;
    var x3 = line2Point1.x;
    var x4 = line2Point2.x;

    var y1 = line1Point1.y;
    var y2 = line1Point2.y;
    var y3 = line2Point1.y;
    var y4 = line2Point2.y;

    var x1Minusx2 = x1 - x2;
    var x3Minusx4 = x3 - x4;
    var y1Minusy2 = y1 - y2;
    var y3Minusy4 = y3 - y4;

    var denominator = x1Minusx2 * y3Minusy4 - y1Minusy2 * x3Minusx4;

    if (Mathf.Approximately(denominator, 0)) return false;

    var a = (x1 * y2 - y1 * x2);
    var b = (x3 * y4 - y3 * x4);
    var ax3MinusX4 = a * x3Minusx4;

    //x
    var numerator = ax3MinusX4 - x1Minusx2 * b;
    var x = numerator / denominator;

    //y
    numerator = ax3MinusX4 - y1Minusy2 * b;
    var y = numerator / denominator;

    intersectionPoint = new Vector2(x, y);

    return true;
}

As you can see from this image - the intersecting point is not being calculated correctly:

Test data:

line1point1 = (2.6, -1.4)
line1point2 = (3.6,-1.3)

line2point1 = (3.5,2.0)
line2point2 = (3.9,1.1)

Gives intersection result: (5.1,1.0)

Where am i going wrong here?

Please provide inline test case (as code with inline data) showing the problem instead of nice animated GIF (you can keep GIF if you like - adds nice touch to the question) — Alexei Levenkov
Not exactly... Something more understandable like "(0,0)(0,2) vs. (1,-1)(1,1) gives XXX instead of (0,1)"... Not everyone can look at sample you've posted and immediately visualize the intersection point... Also writing it as code would make it soo much easier to someone to debug... — Alexei Levenkov

butterflyknife butterflyknife · Accepted Answer · 2020-04-24T00:35:53

First of all, the numerator for y is wrong -- it should be something like numerator = ay3Minusy4 - y1Minusy2 * b;.

Secondly, the correct answer is approximately (4.908511, -1.16915) for the points you've given us (see [1]). Your code is actually correct for x -- I've put it in verbatim into Excel and get 4.908511 as expected, so I don't know what's going on there. This is a long shot, but what's the var type above? Is it some object with weird arithmetical overloads, instead of a float or double?

The values of my intermediate variables to help you debug:

x1Minusx2 == -1.00

x3Minusx4 == -0.40

y1Minusy2 == -0.10

y3Minusy4 == 0.90

denominator == -0.94

a==1.66

b== -3.95

ax3MinusX4 == -0.664

numerX== -4.614

x== 4.908510638

ay3minusy4== 1.494

numerY== 1.099

y== -1.169148936

[1] https://www.wolframalpha.com/input/?i=intersection+of+line+passing+through+%282.6%2C+-1.4%29+and+%283.6%2C-1.3%29+with+the+line+passing+through+%283.5%2C2.0%29+and+%283.9%2C1.1%29

2D Line Line intersection function not working

1 Answers