¿La manera más eficiente de encontrar la distancia entre dos círculos en Java?

Question

Así que aparentemente el cálculo de las raíces cuadradas no es muy eficiente, lo que me deja preguntándome cuál es la mejor manera de averiguar la distancia (que he llamado rango más abajo) entre dos círculos?

Así que normalmente me gustaría trabajar:

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 

Tratando de evitar la raíz cuadrada funciona bien cuando sólo se observa para la situación en la "gama" es 0 para las colisiones:

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

Pero si estoy tratando de calcular esa distancia de rango, termino con una ecuación difícil de manejar como:

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

que no va a ningún lado. Por lo menos yo no sé cómo resolverlo para el rango de aquí ...

La respuesta obvia es, pues, trignometry y primer hallazgo theta:

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

A continuación, el encontrar el hypotemuse Sin (theta) = dy/h h = dy/Sin (theta)

último funciona de la gama gama + r1 + r2 = dy/Sin (theta) rango = dy/sen (theta) - r1 - r2

So th a es lo que he hecho y tengo un método que tiene este aspecto:

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; 

} 

Así que mi pregunta es, es el uso de bronceado y el pecado más eficiente que la búsqueda de una raíz cuadrada?

Podría ser capaz de refactorizar parte de mi código para obtener el valor theta de otro método (donde tengo que resolverlo) ¿valdría la pena hacerlo?

¿O hay otra manera en total?

Por favor, discúlpeme si estoy preguntando lo obvio, o cometer errores elementales, que ha sido un largo tiempo desde que he utilizado las matemáticas de secundaria para hacer cualquier cosa ...

Cualquier consejo o consejos de bienvenida!

**** **** EDITAR

Específicamente Estoy tratando de crear un dispositivo de "scanner" en un juego que detecta cuando los enemigos/obstáculos se están acercando a/ir lejos, etc. El escáner transmitir esta información a través de un tono de audio o una barra gráfica o algo así. Por lo tanto, aunque no necesito números exactos, idealmente me gustaría saber:

1. objetivo está más cerca/más lejos que antes
2. objetivo A está más cerca/más allá de objetivo B, C, D ...
3. Una relación (¿con suerte lineal?) Que expresa qué tan lejos está un objetivo del barco en relación con 0 (colisión) y rango máximo (alguna constante)
4. algunos objetivos serán muy grandes (¿planetas?) Así que tengo que tener en cuenta el radio

Tengo la esperanza de que hay algo de optimización inteligente/aproximación posible (dx + dy + (más larga de dx, dy?), Pero con todos estos requisitos, tal vez no ...

Answer 1

Math.hypot está diseñado para obtener cálculos más rápidos y precisos del formulario sqrt(x^2 + y^2). Por lo que este debe ser sólo

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

No me puedo imaginar cualquier código que sería más sencillo que esto, ni más rápido.

Answer 2

Si realmente necesita la distancia exacta, entonces realmente no se puede evitar la raíz cuadrada. las funciones trigonométricas son al menos tan malo como cálculos de raíz cuadrada, si no peor.

Pero si necesita solo distancias aproximadas de, o si solo necesita distancias relativas para varios peines inaciones de círculos, entonces definitivamente hay cosas que puedes hacer. Por ejemplo, si solo necesita distancias relativas, tenga en cuenta que los números al cuadrado tienen la misma relación mayor que sus raíces cuadradas. Si solo está comparando diferentes pares, omita el paso de raíz cuadrada y obtendrá la misma respuesta.

Si solo necesita distancias aproximadas, puede considerar que h es aproximadamente igual al lado adyacente más largo. Esta aproximación nunca se apaga por más de un factor de dos. O podría usar tablas de búsqueda para las funciones trigonométricas, que son más prácticas que las tablas de búsqueda para raíces cuadradas arbitrarias.

Answer 3

Me cansé de saber si, en primer lugar, las respuestas cuando usamos tan, seno son las mismas que cuando usamos funciones sqrt.

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); 
} 

la respuesta que obtuve fue: 4,700885452542996

1,7008854

5,656854249492381

2,6568542

Ahora parece existir una diferencia entre el valor de los sqrt ser más correcto.

1. hablando ABT la actuación: Tenga en cuenta su fragmento de código:

i calculado el tiempo de la performance, que sale como:

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); 
} 

respuesta - 639,3204215458475, 610,32043, Milisegundos transcurridos: 2

Y cuando probamos con sqrt ro ot uno:

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); 
} 

respuesta - 769,3321779309637, 740.33215, milisegundos transcurrido: 1

Si ahora se busca por la diferencia de la diferencia entre los dos respuesta también es enorme.

por lo tanto, diría que si haces un juego más preciso los datos serían más divertidos, será para el usuario.

Answer 4

El problema generalmente planteado con sqrt en el software de geometría "dura" no es su rendimiento, sino la pérdida de precisión que conlleva. En su caso, sqrt encaja perfectamente.

Si encuentra que sqrt realmente trae multas de rendimiento, ya sabe, optimice solo cuando sea necesario, puede intentarlo con una aproximación lineal.

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

Así, a calcular una tabla de búsqueda (LUT) para sqrt y, dada x, utiliza el x0 más cercano. Por supuesto, eso limita sus posibles rangos, cuando debe recurrir a la informática normal. Ahora, un poco de código.

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); 
    } 
} 

(no he probado este código, por favor, perdona y corregir cualquier error)

Además, después de escribir todo esto, probablemente ya hay alguna biblioteca aproximada, eficiente alternativa de matemáticas por ahí. Debe buscarlo, pero solo si encuentra que el rendimiento es realmente necesario.