Problems getting Circle2D LineSegment2D Intersections

[speedygonz]

Hi, I've been trying to find the intersections between a circle and line segment. However, I can't seem to be able to get any valid intersections when there should be. An example below:

Point2D A = new Point2D(16000.0, 0.0);
Point2D B = new Point2D(-14000.0, 0.0);
Circle2D circle = new Circle2D(0.0, 0.0, 10000.0); //centered at origin with radius 10000.0
LineSegment2D line = new LineSegment2D(A,B);
Collection<Point2D> intersections = circle.intersections(line);

From the points given, there should be two intersections at (10000.0,0.0) and (-10000.0,0.0) but I can't seem to get those points. Am I using the method correctly? If it matters, I'm using java-Geom-0.11.1.jar. Thanks.

[speedygonz]

Did a little more testing. It seems that the "magnitude" of the points makes a difference. I tested with values that are smaller and I managed to obtain 2 valid intersections.

Point2D A = new Point2D(16.0, 0.0);
Point2D B = new Point2D(-14.0, 0.0);
Circle2D circle = new Circle2D(0.0, 0.0, 10.0); //centered at origin with radius 10.0
LineSegment2D line = new LineSegment2D(A,B);
Collection<Point2D> intersections = circle.intersections(line);

Same code but values are 1000x smaller and I get 2 valid intersections at (10.0, 0.0) and (-10.0, 0.0)? This is plain confusing. Can someone help me out here? Is there a "limit" to how big the numbers should be when performing such intersection calculations?

[David]

Hi,

Actually yes, the "magnitude" of the point do matter. This is beause distance computation (used in intersection computations) involves square of coordinate differences, thus amplifying numerical errors.

I do not have any great solution to give. One solution is to reduce the amplitude of the coordinates to stay in an acceptable range (say -1000 -> +1000).
I also know some other libraries like JTS use better error management, like rounding on a linear or logarithmic grid. Sadly I haven't implemented this kind of stuff yet (requires lot of work and checking actually...).

Regards,
David

[speedygonz]

Thanks David for the prompt response. Was hoping to avoid JTS since it does not offer circles/ellipses as native geometry shapes. Instead, the recommended way to model circles is polygons with multiple edges. This feels like a rather imprecise way to model perform calculations. Also, the last update to JTS was back in 2006, I'm not so sure whether there'll be support going ahead. In any case, I'll give it a shot and hope to feedback at some point.