Most efficient way to find distance between two circles in java?
java, math, performance, trigonometry
Solution
`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.
Problem
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: - target is closer/further than before - target A is closer/further than target B, C, D... - A (linear hopefully?) ratio that expresses how far a target is from the ship relative to 0 (collision) and max range (some constant) - 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...