Most common way to compute line line intersection C++?

Question

Seems there is no way to compute line line intersection using boost::geometry, but I wonder what is the most common way to do it in C++?

I need intersection algorithms for two infinite lines in 2D, if it will be faster it can be two different functions like:

bool line_intersection(line,line);
point line_intersetion(line,line);

P.S. I really try to avoid a wheel invention, so incline to use some library.

Answer 1

The best algorithms that I've found for finding the intersection of lines are in: Real Time Collision Detection by Christer Ericson, a copy of the book can be found here.

Chapter 5 from page 146 onwards describes how to find the closest point of 3D lines which is also the crossing point of 2D lines... with example code in C.

Note: beware of parallel lines, they can cause divide by zero errors.

Answer 2

Express one of the lines in parametric form and the other in implicit form:

X = X0 + t (X1 - X0), Y= Y0 + t (Y1 - Y0)

S(X, Y) = (X - X2) (Y3 - Y2) - (Y - Y2) (X3 - X2) = 0

By linearity of the relations, you have

S(X, Y) = S(X0, Y0) + t (S(X1, Y1) - S(X0, Y0)) = S0 + t (S1 - S0) = 0

From this you get t, and from t the coordinates of the intersection.

It takes a total of 15 adds, 6 multiplies and a single divide.

Degeneracy is indicated by S1 == S0, meaning that the lines are parallel. In practice, the coordinates may not be exact because of truncation errors or others, so that test for equality to 0 can fail. A workaround is to consider the test

|S0 - S1| <= µ |S0|

for small µ.