# Exact evaluation of sign of floating point expression

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$$?

• This may help: en.wikipedia.org/wiki/Interval_arithmetic – saulspatz Jul 12 at 13:25
• 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. – Yves Daoust Jul 12 at 13:29
• @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. – Remco Poelstra Jul 12 at 13:37
• @RemcoPoelstra: do you mean thick point-in-polygon ? – Yves Daoust Jul 12 at 13:46
• – lhf Jul 12 at 13:49