I'm trying to determine whether a line (defined by two points) and a circle (defined by three points) intersect. The points use doubles.

In this document the following discriminant is given (formula 6): $\delta=(D\cdot\Delta)^2-|D|^2(|\Delta|^2-R^2)$. When $\delta>0$ there are 2 intersection points, if $\delta=0$ there is 1 intersection point and when $\delta<0$ there are none.

How can I determine the sign of $\delta$ exactly? I'm currently using infinite precision arithmetics, but these calculations are extremely expensive. Is there a way to do it just in floating point?

As an alternative, would it be possible to set an error bound on the calculation and if $|\delta|<\epsilon$ for some (large) $\epsilon$ do the calculation again using infinite precision arithmetics.

I expect that in 90% of the cases the floating point answer will be just fine, so I expect this would speed up the algorithm vastly. I'm just unsure I can set a bound on the final result while there are many calculations up front, as well as how do I determine the right value for $\epsilon$?

  • $\begingroup$ This may help: en.wikipedia.org/wiki/Interval_arithmetic $\endgroup$ – saulspatz Jul 12 at 13:25
  • 1
    $\begingroup$ In the first place, do you have a good reasons to require an exact evaluation ? If the data themselves are noisy (or suffer truncation errors), the outcome can be wrong anyway. And if you find two intersections with a nearly zero discriminant, will their evaluation make sense ? IMO, more context is required. $\endgroup$ – Yves Daoust Jul 12 at 13:29
  • $\begingroup$ @YvesDaoust The algorithm that uses this information (point in polygon check) can fail miserably for edge-cases when the sign is not determined exactly. I'm not trying to actually find the intersections, which is why I'm only interested in the sign if the discriminant. $\endgroup$ – Remco Poelstra Jul 12 at 13:37
  • $\begingroup$ @RemcoPoelstra: do you mean thick point-in-polygon ? $\endgroup$ – Yves Daoust Jul 12 at 13:46
  • $\begingroup$ See also scicomp.stackexchange.com/questions/27777/… $\endgroup$ – lhf Jul 12 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.