Most efficient way to find distance between two circles in java?

Question

So apparently calculating square roots is not very efficient, which leaves me wondering what the best way is to find out the distance (which I've called range below) between two circles is?

So normally I would work out:

a^2 + b^2 = c^2
dy^2 + dx^2 = h^2
dy^2 + dx^2 = (r1 + r2 + range)^2
(dy^2 + dx^2)^0.5 = r1 + r2 + range
range = (dy^2 + dx^2)^0.5 - r1 - r2

Trying to avoid the square root works fine when you just look for the situation when "range" is 0 for collisions:

 if ( (r1 + r2 + 0 )^2 > (dy^2 + dx^2) )

But if I'm trying to work out that range distance, I end up with some unwieldy equation like:

 range(range + 2r1 + 2r2) = dy^2 + dx^2 - (r1^2 + r2^2 + 2r1r2)

which isn't going anywhere. At least I don't know how to solve it for range from here...

The obvious answer then is trignometry and first find theta:

  Tan(theta) = dy/dx
  theta = dy/dx * Tan^-1

Then the find the hypotemuse Sin(theta) = dy/h h = dy/Sin(theta)

Finally work out the range range + r1 + r2 = dy/Sin(theta) range = dy/Sin(theta) - r1 - r2

So that's what I've done and have got a method that looks like this:

private int findRangeToTarget(ShipEntity ship, CircularEntity target){


    //get the relevant locations
    double shipX = ship.getX();
    double shipY = ship.getY();
    double targetX =  target.getX();
    double targetY =  target.getY();
    int shipRadius = ship.getRadius();
    int targetRadius = target.getRadius();

    //get the difference in locations:
    double dX = shipX - targetX;
    double dY = shipY - targetY;

    // find angle 
    double theta = Math.atan(  ( dY / dX ) );

    // find length of line ship centre - target centre
    double hypotemuse = dY / Math.sin(theta);

    // finally range between ship/target is:
    int range = (int) (hypotemuse - shipRadius - targetRadius);

    return range;

}

So my question is, is using tan and sin more efficient than finding a square root?

I might be able to refactor some of my code to get the theta value from another method (where I have to work it out) would that be worth doing?

Or is there another way altogether?

Please excuse me if I'm asking the obvious, or making any elementary mistakes, it's been a long time since I've used high school maths to do anything...

Any tips or advice welcome!

****EDIT****

Specifically I'm trying to create a "scanner" device in a game that detects when enemies/obstacles are approaching/ going away etc. The scanner will relay this information via an audio tone or a graphical bar or something. Therefore although I don't need exact numbers, ideally I would like to know:

1. target is closer/further than before
2. target A is closer/further than target B, C, D...
3. A (linear hopefully?) ratio that expresses how far a target is from the ship relative to 0 (collision) and max range (some constant)
4. some targets will be very large (planets?) so I need to take radius into account

I'm hopeful that there is some clever optimisation/approximation possible (dx + dy + (longer of dx, dy?), but with all these requirements, maybe not...

Answer 1

Math.hypot is designed to get faster, more accurate calculations of the form sqrt(x^2 + y^2). So this should be just

return Math.hypot(x1 - x2, y1 - y2) - r1 - r2;

I can't imagine any code that would be simpler than this, nor faster.

Answer 2

The problem usually brought up with sqrt in "hard" geometry software is not its performance, but the loss of precision that comes with it. In your case, sqrt fits the bill nicely.

If you find that sqrt really brings performance penalties - you know, optimize only when needed - you can try with a linear approximation.

f(x) ~ f(X0) + f'(x0) * (x - x0)
sqrt(x) ~ sqrt(x0) + 1/(2*sqrt(x0)) * (x - x0)

So, you compute a lookup table (LUT) for sqrt and, given x, uses the nearest x0. Of course, that limits your possible ranges, when you should fallback to regular computing. Now, some code.

class MyMath{
    private static double[] lut;
    private static final LUT_SIZE = 101;
    static {
        lut = new double[LUT_SIZE];
        for (int i=0; i < LUT_SIZE; i++){
            lut[i] = Math.sqrt(i);
        }
    }
    public static double sqrt(final double x){
        int i = Math.round(x);
        if (i < 0)
            throw new ArithmeticException("Invalid argument for sqrt: x < 0");
        else if (i >= LUT_SIZE)
            return Math.sqrt(x);
        else
            return lut[i] + 1.0/(2*lut[i]) * (x - i);
    }
}

(I didn't test this code, please forgive and correct any errors)

Also, after writing this all, probably there is already some approximate, efficient, alternative Math library out there. You should look for it, but only if you find that performance is really necessary.

Answer 3

I tired working out whether firstly the answers when we use tan, sine is same as when we use sqrt functions.

public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
     double shipX = 5;
        double shipY = 5;
        double targetX =  1;
        double targetY =  1;
        int shipRadius = 2;
        int targetRadius = 1;

        //get the difference in locations:
        double dX = shipX - targetX;
        double dY = shipY - targetY;

        // find angle 
        double theta = Math.toDegrees(Math.atan(  ( dY / dX ) ));

        // find length of line ship centre - target centre
        double hypotemuse = dY / Math.sin(theta);
        System.out.println(hypotemuse);
        // finally range between ship/target is:
        float range = (float) (hypotemuse - shipRadius - targetRadius);
        System.out.println(range);

        hypotemuse = Math.sqrt(Math.pow(dX,2) + Math.pow(dY,2));
        System.out.println(hypotemuse);
        range = (float) (hypotemuse - shipRadius - targetRadius);
        System.out.println(range);
}

The answer which i got was : 4.700885452542996

1.7008854

5.656854249492381

2.6568542

Now there seems a difference between the value with sqrt ones being more correct.

1. talking abt the performance : Consider your code snippet :

i calculated the time of performance- which comes out as:

    public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
    long lStartTime = new Date().getTime(); //start time
    double shipX = 555;
        double shipY = 555;
        double targetX =  11;
        double targetY =  11;
        int shipRadius = 26;
        int targetRadius = 3;

        //get the difference in locations:
        double dX = shipX - targetX;
        double dY = shipY - targetY;

        // find angle 
        double theta = Math.toDegrees(Math.atan(  ( dY / dX ) ));

        // find length of line ship centre - target centre
        double hypotemuse = dY / Math.sin(theta);
        System.out.println(hypotemuse);
        // finally range between ship/target is:
        float range = (float) (hypotemuse - shipRadius - targetRadius);
        System.out.println(range);


        long lEndTime = new Date().getTime(); //end time

          long difference = lEndTime - lStartTime; //check different

          System.out.println("Elapsed milliseconds: " + difference);
}

Answer - 639.3204215458475, 610.32043, Elapsed milliseconds: 2

And when we try out with sqrt root one:

public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
    long lStartTime = new Date().getTime(); //start time
    double shipX = 555;
        double shipY = 555;
        double targetX =  11;
        double targetY =  11;
        int shipRadius = 26;
        int targetRadius = 3;

        //get the difference in locations:
        double dX = shipX - targetX;
        double dY = shipY - targetY;

        // find angle 
        double theta = Math.toDegrees(Math.atan(  ( dY / dX ) ));

        // find length of line ship centre - target centre

       double hypotemuse = Math.sqrt(Math.pow(dX,2) + Math.pow(dY,2));
        System.out.println(hypotemuse);
        float range = (float) (hypotemuse - shipRadius - targetRadius);
        System.out.println(range);

        long lEndTime = new Date().getTime(); //end time

          long difference = lEndTime - lStartTime; //check different

          System.out.println("Elapsed milliseconds: " + difference);
}

Answer - 769.3321779309637, 740.33215, Elapsed milliseconds: 1

Now if we check for the difference the difference between the two answer is also huge.

hence i would say that if you making a game more accurate the data would be more fun it shall be for the user.

Answer 4

If you really need the accurate distance, then you can't really avoid the square root. Trigonometric functions are at least as bad as square root calculations, if not worse.

But if you need only approximate distances, or if you need only relative distances for various combinations of circles, then there are definitely things you can do. For example, if you need only relative distances, note that squared numbers have the same greater-than relationship as do their square roots. If you're only comparing different pairs, skip the square root step and you'll get the same answer.

If you only need approximate distances, then you might consider that h is roughly equal to the longer adjacent side. This approximation is never off by more than a factor of two. Or you could use lookup tables for the trigonometric functions -- which are more practical than lookup tables for arbitrary square roots.