How to calculate the point of intersection between two lines

Question

I am attempting to calculate the point of intersection between lines for a Optical Flow algorithm using a Hough Transform. However, I am not getting the points that I should be when I use my algorithm for calculating the intersections.

I save the Lines as an instance of a class that I created called ImageLine. Here is the code for my intersection method.

Point ImageLine::intersectionWith(ImageLine other)
{
    float A2 = other.Y2() - other.Y1();
    float B2 = other.X2() - other.X1();
    float C2 = A2*other.X1() + B2*other.Y1();

    float A1 = y2 - y1;
    float B1 = x2 - x1;
    float C1 = A1 * x1 + B1 * y1;

   float det = A1*B2 - A2*B1;
   if (det == 0)
   {
        return Point(-1,-1);
   }
   Point d = Point((B2 * C1 - B1 * C2) / det, -(A1 * C2 - A2 * C1) / det);
   return d;
}

Is this method correct, or did I do something wrong? As far as I can tell, it should work, as it does for a single point that I hard-coded through, however, I have not been able to get a good intersection when using real data.

Solution 1

Considering the maths side: if we have two line equations:

y = m1 * x + c1
y = m2 * x + c2

The point of intersection: (X , Y), of two lines described by the following equations:

Y = m1 * X + c1
Y = m2 * X + c2

is the point which satisfies both equation, i.e.:

m1 * X + c1 = m2 * X + c2
(Y - c1) / m1 = (Y - c2) / m2

thus the point of intersection coordinates are:

intersectionX = (c2 - c1) / (m1 - m2)
intersectionY = (m1*c1 - c2*m2) / m1-m2 or intersectionY = m1 * intersectionX + c1

Note: c1, m1 and c2, m2 are calculated by getting any 2 points of a line and putting them in the line equations.

Solution 2

(det == 0) is unlikely to be true when you're using floating-point arithmetic, because it isn't precise.

Something like (fabs(det) < epsilon) is commonly used, for some suitable value of epsilon (say, 1e-6).

If that doesn't fix it, show some actual numbers, along with the expected result and the actual result.

Solution 3

For detailed formula, please go to this page.

But I love code so, here, check this code (I get it from github, so all credit goes to the author of that code):

///Calculate intersection of two lines.
///\return true if found, false if not found or error
bool LineLineIntersect(double x1, double y1, //Line 1 start
    double x2, double y2, //Line 1 end
    double x3, double y3, //Line 2 start
    double x4, double y4, //Line 2 end
    double &ixOut, double &iyOut) //Output 
{
    //http://mathworld.wolfram.com/Line-LineIntersection.html

    double detL1 = Det(x1, y1, x2, y2);
    double detL2 = Det(x3, y3, x4, y4);
    double x1mx2 = x1 - x2;
    double x3mx4 = x3 - x4;
    double y1my2 = y1 - y2;
    double y3my4 = y3 - y4;

    double xnom = Det(detL1, x1mx2, detL2, x3mx4);
    double ynom = Det(detL1, y1my2, detL2, y3my4);
    double denom = Det(x1mx2, y1my2, x3mx4, y3my4);
    if(denom == 0.0)//Lines don't seem to cross
    {
        ixOut = NAN;
        iyOut = NAN;
        return false;
    }

    ixOut = xnom / denom;   
    iyOut = ynom / denom;
    if(!isfinite(ixOut) || !isfinite(iyOut)) //Probably a numerical issue
        return false;

    return true; //All OK
}

Comments

[AndrewSchade]

When dealing with real data, nearly parallel lines are also unlikely... but that isn't the real issue, what happens is that where real lines are supposed to intersect is not returned. (I visually display the data for debugging purposes.

[Useless]

So what is returned? What are your inputs? What are the intermediate values?