[Prog] Distancias entre 2 puntos

Archivado
Buenas
Me gustaria hacer un programa para calcular la distancia entre 2 puntos, la única forma que se me ocurre es hacer:
Raiz( cuadrado(x2-x1) + cuadrado(y2-y1) )
pero necesito que el programa sea rápido, entonces desearia saber si es que existe alguna otra forma más optima para realizar ese calculo.

Gracias :-P
¿Y no te sirve una excel?
No sé si existe otra forma de hacerlo rápido.

Pero en un programa, esas operaciones son rápidas de usar. Quizás es que no sabemos que o como lo quieres hacer.

Si te sirve en JAVA te paso como se hace, pero paso por paso, osea, la forma más "larga" de hacerlo:

public double tamany(){
double tmp1;
tmp1 = pB.retX();
tmp1 = tmp1 - pA.retX();
tmp1 = tmp1*tmp1;
double tmp2;
tmp2 = pB.retY();
tmp2 = tmp2 - pA.retY();
tmp2 = tmp2*tmp2;
return (java.lang.Math.sqrt(tmp1 + tmp2));
}


La funcion cálculo el tamaño formado por dos puntos, donde pA y pB son esos puntos y son otra clase. Me parece fácil el resto, pero si lo necesitas te lo explico paso por paso.
Pues lo que deseo hacer, es resolver un probema que es el siguiente:
Tengo coordenadas, para pozos y casas.
El numero de casas entre pozos siempre dará un entero.
Y me gustaria unir a cada pozo un numero de casas, tal que la suma de todas las distancias sea la minima. La suma de todas las distancias tiene que ser la minima, vamos para gastar menos en tuberias :D
Y me gustaria hacerlo en un tiempo computacional muy bajo, por eso queria saber si habia algún metodo más rápido para calcular las distancias.

Si alguien tiene alguna idea; aunque creo que habrá que tirar de metodos matemáticos.
Si tienes una necesidad REAL de que el código sea extremadamente rápido, puedes inspirarte en el código que John Carmack usó en Quake III para hacer la raíz cuadrada inversa (inv sqrt()). Básicamente, usa el método de aproximación de Newton-Raphson con un valor inicial muy inteligente.

Tu caso no es exactamente el mismo código (el tuyo es sqrt()), pero sigues pudiendo usar el método de Newton.

http://www.beyond3d.com/articles/fastinvsqrt/
Aquí tienes un enlace con el código original.

http://www.sosmath.com/calculus/diff/der07/der07.html
Y aquí tienes el método de Newton-Raphson, que verás que converge muy rápidamente (hasta 10 decimales exactos en 5 iteraciones).

Saludos [beer]

EDITO: bah, realmente no creo que te merezca la pena (a menos que no puedas usar la librería Math). Ya que en realidad, los métodos de las librerías matemáticas están implementados de formas casi óptimas. Yo haría un Math.sqrt(x1*x2+y1*y2).
Gracias Det_W.Somerset [plas] al final sera mejor usar lo que ya esta implementado, porque supongo que optimizaran bastante, no iran a hacer un código legible, sino más hacia la optimización. Son más las veces que se usa la función, que las que uno se para a ver su implementación.

Por otro lado, alguien tiene alguna idea de cómo se podria solucionar el problema de conseguir la suma minima de las distancias?
Si la posicion de las "casas" y los "pozos" son fijas, puedes precalcular las distancias en una tabla cuadrada d(Ci, Pj).

Es un metodo parecido al que usan algunos programas, tienen tablas precalculadas de senos y cuando necesitan un valor hacen una interpolacion que es mas rapida (aunque el resultado tenga errores).

No entiendo tu problema.
Supongo que la superficie en los que se encuentran los objetos es plana, pues si no fuera asi, la distancia mas corta no seria la recta.

¿Que quiere decir "El numero de casas entre pozos siempre dará un entero."?, el "numero de casas" siempre ha sido un entero, mas precisamente un numero natural, carece de sentido hablar de "media casa" o pi casas

buscas minimizar "la suma de todas las distancis", intuyo que quieres decir de la red construida, pero ¿que condiciones debe cumplir esa red?. ¿Que todas las casas esten unidas al menos a un pozo?

Si precisas un poco mas el problema intentare ayudarte.
6 respuestas
Archivado
Volver a General