# Robust two lines/segments intersection point in 2D

Given two line segments the problem is to find an intersection point of corresponding lines (assuming that they are not parallel or coincide).

There is a Wikipedia article which gives us exact formulas, but there are two of them: one that uses t ratio and approaches intersection point from first line segment and the other -- uses u and the second line segment. How can I select which one to use in my scenario?

For example: my initial implementation which always used t failed on

first_segment = Segment(start=Point(x=-5, y=0), end=Point(x=72057594037954921, y=0))
second_segment = Segment(start=Point(x=0, y=0), end=Point(x=0, y=3))


gives

Point(x=5.921189464665284e-16, y=0.0)


which is incorrect, but when I switch to use u or change order of arguments it gives me correct

Point(x=0.0, y=0.0)


So my question is: is there robust way to calculate intersection point?

If you choose a formula with parameter $$t$$ you'll get the $$P_x$$ value as a result of a number of operations - additions, multiplications and one division:

$$t = \frac{(x_1-x_3)(y_3-y_4)-(y_1-y_3)(x_3-x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)}$$ $$P_x = x_1 + t(x_2-x_1)$$

The number $$x_2=72057594037954921$$ contains 17 significant decimal digits - so it can't be represented exactly using double-precision floating numbers. Apparently, a small error is introduced during some operation (most probably - the division), and this error is propagated to the result. This is a form of the Round-off error.

This bunch of calculations doesn't happen when you choose a formula with parameter $$u$$, because the numerator there is equal to zero.

Conclusion: if you need to work with numbers, containing a big number of significant digits - use floating numbers with bigger precision, or may be - with arbitrary precision. An example: mpmath.

Another option - use rational numbers. For example, kernels, based on rational numbers, can be found in the computational geometry library CGAL. Developers of this library have invested a lot of efforts to solve this robustness problem - please see this page for more information.

If you want to go deeper into this research area, called Exact Geometric Computation (EGC), you can start from this review. You'll need a good knowledge of Linear Algebra and Linear Systems.

• so can I detect whether to use t or u based on absolute value of $x_2$? – Azat Ibrakov Feb 1 at 8:16
• btw I'm using Python with double precision floating point numbers if it matters – Azat Ibrakov Feb 1 at 8:16
• @AzatIbrakov - if you need to find an intersection of two segments you'll have to calculate both $t$ and $u$ and make sure that $0 \le t \le 1$ and $0 \le u \le 1$. Your example shows, that in this case you can get two intersection points... which one would you choose? You can't get an exact result from inexact intermediate calculations – HEKTO Feb 1 at 17:10