3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ so can I detect whether to use t or u based on absolute value of $x_2$? $\endgroup$ Feb 1, 2020 at 8:16
  • $\begingroup$ btw I'm using Python with double precision floating point numbers if it matters $\endgroup$ Feb 1, 2020 at 8:16
  • $\begingroup$ @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 $\endgroup$
    – HEKTO
    Feb 1, 2020 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.