CODEWITHSUNDEEP
c++opencvlineintersection
AndrewSchade
AndrewSchade

Reputation: 61

How to calculate the point of intersection between two lines

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.

Upvotes: 5

Views: 35746

Answers (4)

123iamking
123iamking

Reputation: 2703

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):

Edit: prepended code from the github link without this excerpt couldn't even compile.

#include <iostream>
#include <cmath>
#include <assert.h>
using namespace std;

/** Calculate determinant of matrix:
        [a b]
        [c d]
*/
inline double Det(double a, double b, double c, double d)
{
        return a*d - b*c;
}
///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
}

Upvotes: 2

sethi
sethi

Reputation: 1889

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.

Upvotes: 8

NPAssoc
NPAssoc

Reputation: 395

Assuming your formulas are correct, try declaring all your intermediate arguments as 'double'. Taking the difference of nearly parallel lines could result in your products being very close to each other, so 'float' may not preserve enough precision.

Upvotes: 1

Useless
Useless

Reputation: 67743

(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.

Upvotes: 3

Related Questions