IntrEllipse2Ellipse2

[leigangarcsite]

hi, i meet a problem with ellipse intersect with ellipse

circle1 point(0,0) radius(500)
circle2 point(500,0) radius(200)

circle2 intersectWith circle1 failed
circle1 intersectWith circle2 ok

this could be due to floating-point precision limitations.

Will error tolerance be added for intersections? Tangent ellipse-circle cases rarely yield exact solutions due to FP limit

[davideberly]

Yes, the problem is floating-point rounding error. The file ErrorFindIntersectionEllipses.cpp is a comparison of using the find-intersection query for types float, double, and rational. The rational version computes accurate intersection points. These might not be exact because the computations involve polynomial root finding, where the roots are irrational.

In the float and double versions I have comments that show the values of e3 that are tested on line 548 of IntrEllipse2Ellipse2.h. The e3 value is the coefficient of the squared term in a quadratic equation. The theoretical value is zero. For float, the value is -7.27595760e-18. For double, the value is -1.3552527156068805e-26. The difference in magnitudes should make it clear that choosing an "error tolerance" is going to be difficult. It depends on whether you use float or double, and it depends on the magnitudes of the ellipse input numbers.

Your only option for now is to use rational arithmetic. I am looking at the derivation in the PDF associated with the algorithm to determine whether I can create something more robust for floating-point. However, this is the typical type of problem in computational geometry. The algorithm depends on exact classification of signs. This requires rational arithmetic.

For sign classification, the computational geometers are fond of telling folks to use interval arithmetic to improve the performance over fully using rational arithmetic. Unfortunately, this does not work in practice. Changing the rounding mode on the floating-point hardware unit is very expensive, more so than using rational arithmetic when you have numbers with small precision, which sign classifications have for the ellipse intersection problem, and when you have many arithmetic operations. See FPInterval.h. Instead, you can get intervals by using floating-point bit patterns and rounding up or down, but this is also expensive. See SWInterval.h In the end, my choice is simply to use rational arithmetic. Yes, you pay a performance cost compared to only floating-point, but I prefer to have an accurate answer slowly rather than an inaccurate one quickly.

[leigangarcsite]

Thanks David, I’ll test your recommendation

[leigangarcsite]

I tried rational, but it was too time-consuming. Then I read about your RobustIntersectionOfEllipses and realized that an excessively large denominator could reduce the number of significant digits. So I attempted to reduce the denominator and made the following modifications. The solving part was also modified accordingly, and it seems to perform decently. maybe formula XMX=1 change to XM'X=A， The ultimate solution still requires a Multiple Precision Arithmetic Library

[leigangarcsite]

Recently, I experimented with lib2geom's ellipse.cpp and ARB. When solving equations, epsilon is required to handle near-zero cases, while ARB is generally needed for precision control in arithmetic operations to maintain significant digits.