0

I know there are tons of examples to do this. But I need to understand what I'm doing.

Could you please tell me the error in this code?

Point[] intersections(Circle c) 
{
    Point p0 = new Point(center);
    Point p1 = new Point(c.center);
    double d, x, y;
    d = p0.distance(p1);
    if(radius + c.radius < d || Math.abs(radius - c.radius) > d)
        return null;                
    x = (d*d - c.radius*c.radius + radius*radius)/(2*d);
    y = Math.sqrt(radius*radius - x*x);
    if(Double.isNaN(y))
        return null;
    double y0 = y;
    double y1 = -1*y;
    Point i0 = new Point(x,y0,0);
    Point i1 = new Point(x,y1,0);
    i0 = i0.add(p0);
    i1 = i1.add(p1);
    return new Point[]{i0, i1};
}

I have 2 circles c0 and c1. When I write
c0.intersections(c1), the output is:

5.162277660168379 14.32455532033676 0.0
8.162277660168378 2.675444679663241 0.0

And if I switch the order:
c1.intersections(c0), the output is:

5.0 15.32455532033676 0.0
2.0 1.675444679663241 0.0

1 Answer 1

1

There are two problems I see: the intersections aren't right (I went and implemented a full test case with your code), and the intersections shouldn't depend on the ordering of points.

Let's go through a simple example. What happens when we have circles each of radius 1 and centered at (0,0) and (1,1)? Then we get

x = 1/sqrt(2)
y = 1/sqrt(2)
y0 = 1/sqrt(2)
y1 = -1/sqrt(2)

Now, I'm going to assume your add method just adds the coordinates of points together. If so, then we get

Point i0 centered at (1/sqrt(2) + 0, 1/sqrt(2) + 0)
Point i1 centered at (1/sqrt(2) + 1, -1/sqrt(2) + 1)

Which is clearly not right as the intersections for two such circles should be (1,0) and (0,1). And if you reverse the order of points in your intersection call, everything is exactly the same except we add +1 and +1 to the first point, but +0 and +0 to the second point, which turns out to be a different answer! To fix this, you need to change which coordinate gets negated.

It would help to know where you got these formulas you're using. For instance, if the centers can be expressed as (0,0) and (d,0), then your formula for x suffices (see here), but this doesn't hold for most pairs of circles. And I have no idea how you got the y formula, so I suggest checking your derivations for x and y.

I would just implement the procedure here.

2
  • And I have no idea how you got the y formula it is in the link you have pasted.
    – padawan
    May 30, 2014 at 19:41
  • The wolfram alpha one or the math overflow one? If it's the former, I did the calculation and could not simplify it down to what you got. And in any case, that link assumes the points can be expressed as if they are (0,0) and (d,0), which is clearly not true in the general case. May 30, 2014 at 19:51

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.