No conozco ningún algoritmo de distancia que sea más eficiente que aplicar la fórmula de distancia euclidiana (que es simplemente el Pythogorean en forma de geometría coordinada).
Suponiendo que desea la distancia euclidiana entre los puntos [matemática] (x_1, y_1) [/ matemática] y [matemática] (x_2, y_2) [/ matemática], puede dividirla fácilmente en sus operaciones elementales.
Para hacer esto, deberá aplicar los siguientes conceptos:
- ¿Existe una razón intuitiva por la cual la hipótesis Continuum es indecidible?
- ¿Se requiere arte para producir conocimiento en matemáticas?
- Dado que cualquier cadena finita de dígitos debe aparecer en una serie infinita de dígitos generados aleatoriamente, ¿esto implica que también debe aparecer una cadena infinita?
- ¿Puedo obtener una oferta condicional de Cambridge for Mathematics si aún no tengo nada con qué impresionarlos?
- ¿Por qué encontramos algo más difícil de entender que otros, incluso si no fuera abstracto? Por ejemplo, ¿por qué encontramos algunos problemas matemáticos más difíciles que otros?
- La potencia más alta que necesitará para aumentar un número en este caso es 2 (es decir, un cuadrado). Una operación cuadrada es solo una operación aritmética simple, por ejemplo, [math] x ^ 2 = x \ cdot x [/ math]
- Una raíz cuadrada (que es donde reside la penalización de rendimiento) se puede calcular utilizando una variedad de métodos. Vea aquí una lista de métodos: http://en.wikipedia.org/wiki/Met…
La mayoría de ellos se basan solo en operaciones aritméticas. - Luego, simplemente aplique lo anterior a la fórmula de distancia euclidiana para obtener la distancia que necesita, hasta un nivel específico de precisión numérica:
[matemáticas] d = \ sqrt {(x_1 – x_2) ^ 2 + (y_1 – y_2) ^ 2} [/ matemáticas]
Dicho esto, dudo que esto sea más rápido que simplemente programar la fórmula de distancia euclidiana directamente en el lenguaje de programación de su elección. La mayoría de los lenguajes tienen implementaciones integradas de bajo nivel de sqrt()
que probablemente serán más eficientes que cualquier solución manual.
Observaciones
- Si solo está comparando dos distancias, ni siquiera necesita realizar la operación de raíz cuadrada: solo compare las distancias cuadradas.
- Si solo desea una aproximación rápida de la distancia, estos artículos pueden ser de su interés.
Funciones rápidas de distancia aproximada: http://www.flipcode.com/archives…
Implementación de raíz cuadrada inversa de Quake III: http://www.codemaestro.com/revie…