Si tuviera un millón de puntos en 2D, ¿cómo calcularía efectivamente la distancia de un punto a cualquier otro punto?

Answer 1

Sí, de hecho, no hay atajos. Si quieres todas las distancias tienes que calcularlas todas.

Sin embargo, si su pregunta fue provocada por un problema real del mundo real, puede estar satisfecho con las soluciones aproximadas.

Si es así, aquí hay algunas ideas para ayudarlo:

• Si solo está comparando distancias, en realidad no necesita la distancia en sí, puede usar la distancia al cuadrado y evitar raíces cuadradas innecesarias y costosas.
• La distancia de Manhattan es menos precisa pero más rápida que la distancia euclidiana.
• Si solo necesita encontrar N puntos más cercanos, considere usar algo como un árbol kd, quadtree o árbol BSP.
• Si sus partículas tienen una interacción de corto alcance entre sí, como en una simulación de fluidos como la hidrodinámica de partículas suavizadas (SPH), puede usar una cuadrícula uniforme de cubos para acelerar los cálculos.
• Otra idea, al colocar los puntos en una cuadrícula uniforme, puede calcular las distancias reales a los puntos en los cubos cercanos, pero simplemente use la distancia al centro del cubo como una medida aproximada para todos los puntos en los cubos más distantes.
• Y finalmente, es posible que pueda usar la GPU para acelerar mucho esto.

Answer 2

Suponiendo que cuando escribes un punto, significa que ese punto es la fuente, y necesitamos encontrar la distancia desde ese punto a cualquier otro punto, entonces puede tratarse como un problema de la teoría de grafos. El mejor método para resolverlo es usar el algoritmo de Dijkstra para resolver el problema de la ruta más corta de una sola fuente. Su complejidad temporal es O (| E | + | V | log | V |), donde, E es el número de aristas y V es el número de vértices (suponiendo que el gráfico esté conectado).

Para distancias desde cada punto a cualquier otro punto, tenemos que usar repetidamente el algoritmo n veces para n número de puntos.

Answer 3

Editar: si desea averiguar la distancia desde un punto a cualquier otro punto, es solo [matemática] \ Theta (n) [/ matemática] ya que debe considerar [matemática] n – 1 [/ matemática] puntos y calcular [matemáticas] n – 1 [/ matemáticas] distancias.

Si desea calcular las distancias desde cada punto a cualquier otro punto, entonces–
Si todos los puntos son distintos, debe considerar cada par de puntos al menos una vez, por lo que el mejor algoritmo sería [matemática] \ Theta (n ^ 2) [/ matemática] porque tendría que calcular [matemática] \ dfrac {n (n-1)} {2} [/ matemáticas] distancias.

Answer 4

Posiblemente un complemento a la excelente respuesta de Dale Thomas: es posible que el problema que está tratando de resolver se satisfaga con la distancia al centro de la barra de todos los puntos. Eso le daría 1M * 2 de tiempo en lugar de 1M ^ 2.

Answer 5

No hay atajos, debe calcular la distancia de cada punto a cada uno; es una operación N ^ 2

Answer 6

La pregunta es acerca de encontrar la distancia desde un punto a cualquier otro punto. Esta será solo la solución O (n), es decir, calcular la distancia desde ese punto en particular a todos los demás puntos.