algorithm - mas - problema del par de puntos más cercano

Algoritmo para calcular las distancias entre muchos puntos geo

Question

Tengo una matriz que tiene alrededor de 1000 puntos geoespaciales (longitud, latitud) y estoy tratando de encontrar los puntos que están en el rango de 1 km.

NOTA: "Los puntos son dinámicos, los vehículos Imagine 1000 se están moviendo, así que tengo que volver a calcular todas las distancias cada pocos segundos"

Hice algunas búsquedas y leí sobre algoritmos de grafos como (Floyd – Warshall) para resolver esto, y terminé con muchas palabras clave, y ahora estoy un poco perdido. Estoy considerando el rendimiento y como el radio de búsqueda es corto, no consideraré la curvatura de la tierra.

Básicamente, parece que tengo que calcular la distancia entre cada punto a cada otro punto, luego ordenar las distancias a partir de cada punto en la matriz y obtener los puntos que están en su rango. Entonces, si tengo 1000 coordenadas, tengo que realizar este proceso (1000 ^ 2-1000) veces y no creo que esta sea la solución óptima. Gracias.

Answer 1

Creo que tengo algo parecido en una página web en la que trabajé. El usuario hace clic en una ubicación en el mapa e ingresa un radio, y una función devuelve todas las ubicaciones dentro de una base de datos dentro del radio dado. ¿Quiere decir que está tratando de encontrar los puntos que están dentro de 1 km de uno de los puntos en el radio? ¿O estás tratando de encontrar los puntos que están a 1 km uno del otro? Creo que deberías hacer algo como esto.

radius = given radius
x1 = latitude of given point;
y1 = longitude of given point;
x2 = null;
y2 = null;
x = null;
y = null;
dist = null;

for ( i=0; i<locationArray.length; i++ ) {
    x2 = locationArray[i].latitude;
    y2 = locationArray[i].longitude;
    x = x1 - x2;
    y = y1 - y2;
    dist = sqrt(x^2 + y^2);
    if (dist <= radius)
        these are your points
}

Si está tratando de calcular todos los puntos que están a 1 km de otro punto, podría agregar un bucle externo que proporcione la información de x1 y y1, lo que hará que el bucle interno pruebe la distancia entre el punto dado y cualquier otro punto. dando cada punto en su matriz como entrada. Los cálculos no deberían tomar mucho tiempo, ya que es muy básico.

Answer 2

En su caso, debería mirar el GeoHash que le permite consultar rápidamente las coordenadas dentro de una distancia determinada.

Para su información, MongoDB utiliza geohash internamente y su rendimiento es excelente.

Answer 3

Podría calcular códigos geográficos de un rango de 1 km alrededor de cada una de esas 1000 coordenadas y verificar si algunos puntos están dentro de ese rango. Puede que no sea óptimo, pero te ahorrarás algo de clasificación.

Answer 4

Probar con un R-Tree. El R-Tree admite la operación para encontrar todos los puntos más cercanos a un punto dado que no estén más lejos que un radio determinado. El tiempo de ejecución es óptimo y creo que es O (number_of_points_in_the_result).

Answer 5

Si desea buscar la matriz para cada punto frente a cada punto, entonces ya tiene la fórmula correcta (1000 ^ 2-1000). No hay ningún atajo para este cálculo. Sin embargo, cuando sabe dónde comenzar la búsqueda y desea buscar puntos dentro de un radio de 1 km, puede usar una cuadrícula o un algoritmo espacial para acelerar la búsqueda. Lo más probable es que use un algoritmo de dividir y conquistar y el más barato es un geohash o una curva az. También puedes probar un kd-tree. Tal vez esto sea aún más simple. Pero si tus puntos están en el espacio euclidiano, entonces hay un método planar que se describe aquí: en.wikipedia.org/wiki/Closest_pair_of_points_problem .

Edición: cuando digo 1000 ^ 2-1000, me refiero al tamaño de la cuadrícula, pero en realidad son 1000 ^ (1000 - 1) / 2 pares de puntos, así que mucho menos matemática.

Answer 6

Si realiza un modelo con una cuadrícula de 1 km de espacio:

  0   1    2    3
 ___|____|____|____
0   |    |    |
   c|   b|a   |   d
 ___|____|____|____
1   |    |    |
    |    |f   |
 ___|e___|____|____
2   |    |g   | 

Supongamos que su punto de partida es a. Si su cuadrícula es del tamaño de 1 km, los puntos en el alcance de 1 km deben estar en la misma celda o en uno de los 8 vecinos (Puntos b, d, e, f).

Cada otra celda puede ser ignorada (c, g).

Si bien d es casi de la misma distancia que a c, c puede soltarse antes, porque existen 2 barreras para cruzar, mientras que a y se encuentran en áreas opuestas de su borde y, por lo tanto, están a casi 2 km de distancia.

Para una caída temprana del elemento, puede excluirlo, basta con comprobar la parte x o y de la coordenada. Como a pertenece a (0,2), si x es 0 o menor, o> 3, el punto ya está fuera de rango.

Después de filtrar solo algunos candidatos, puede utilizar la búsqueda exhaustiva.

Answer 7

Tuve el mismo problema pero en el desarrollo de un servicio web En mi caso, para evitar el problema del tiempo de cálculo, utilicé una solución simple de dividir y conquistar: la idea era iniciar el cálculo de la distancia entre el nuevo punto y los demás en cada nueva inserción de datos. , para que mi aplicación acceda directamente a la distancia entre los puntos de arrastre que ya se habían calculado y colocó en mi base de datos