How to calculate the intersection point between two lines

Question

I am trying to calculate the line intersection point for an optical flow algorithm using the Hough transform. However, I do not get points, which should be when I use my algorithm to calculate intersections.

I save the lines as an instance of the 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 have I done something wrong? As far as I can tell, it should work, as well as for one point that I hard-coded, however, I could not get a good intersection when using real data.

Answer 1

Given the side of mathematics: if we have two linear equations:

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

Intersection Point: (X, Y) of two lines described by the following equations:

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

is a point that satisfies both equations, i.e.:

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

thus the intersection coordinate points:

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

Note: c1, m1 and c2, m2 are calculated by obtaining any two points of the line and placing them in linear equations.

Answer 2

(det == 0) unlikely to be true if you use floating point arithmetic because it is not exact.

Something like (fabs(det) < epsilon) usually used for some suitable epsilon value (say 1e-6 ).

If this is not corrected, show some actual numbers along with the expected result and the actual result.

Answer 3

Assuming your formulas are correct, try declaring all your intermediate arguments as "double". Unlike almost parallel lines, your products can be very close to each other, so a "float" may not be accurate enough.