Obtener la distancia más corta desde un punto

Tengo esta tabla en sqlite

Locations ID Lat ( latitude) Lon ( longitude) Type Name City 

Tengo por ejemplo 100 registros lo que necesito es obtener (usando mis propias coordenadas) el punto más cercano en mi tabla.

Lo que hice es conseguir la distancia más corta entre mi punto actual y cada uno en la tabla, y devolver el más corto, pero estoy buscando una mejor solución

Gracias

Una posible solución es utilizar una cuadrícula para todo el mapa que le interesa y asignar previamente puntos a una fila / columna en particular. Entonces:

  1. Calcular la ubicación de la cuadrícula de su nuevo punto: añada una columna a la base de datos para esto.
  2. Calcular la distancia de todas las coordenadas en la cuadrícula actual – si existe
  3. Aún es necesario calcular todas las distancias en la próxima cuadrícula (es poco probable que esté perfectamente centrado en su cuadrado actual, siempre debe comprobar una distancia de la cuadrícula de la que su mejor partido fue pulg).

Debe reducir mucho el número de cálculos que necesita hacer.

Si esperas encontrar siempre una ubicación dentro de la distancia X, puedes consultar las coordenadas x / y que caerán dentro de ese rango de tus coordenadas +/- x KM (un cuadrado), calcula si luego caen dentro del círculo xKM de tu punto, y luego elegir la más corta.

ACTUALIZACIÓN – opción de cuadrícula

Estoy asumiendo que ya están haciendo la distancia entre dos puntos de cálculo y no lo describirán.

Si tienes un atlas a mano puedes ver un ejemplo buscando un lugar en el índice. Le dará una página y una ubicación de cuadrícula como M5. Si va a esa página tendrá filas y columnas etiquetadas con números y letras y si miras en el cuadrado donde la fila M y la columna 5 se cruzan encontrarás la ciudad allí. Para hacerlo por su sistema es necesario:

  1. determinar qué tan grande debe ser su cuadrícula (cuan densos son sus puntos – no sería bueno tener una rejilla grande y todos sus puntos en un cuadrado).
  2. Para cada punto, calcúlese la cuadrícula en la que se encuentra. Si sus polígonos son complejos, hay toneladas de punto en el código de polígono que hay para copiar. Si (como mi ejemplo es) sólo utiliza cuadrados, sólo tiene que determinar qué fila / columna cada punto está entre.
  3. Ver mapa para la ubicación del usuario y los puntos más cercanos ejemplo:

introduzca la descripción de la imagen aquí

Así que si el usuario es el marcador verde, estaría en C4. Usted buscaría todos los otros puntos en C4 y determinaría que el más cercano es # 2. Entonces también tendrías que comprobar una cuadrícula en todo el camino alrededor para asegurarse de que no había un elemento más cercano que el que encontró, por lo que esto incluye cuadrados: B3, B4, B5, C3, C5, D3, D4, D5 . Cuando lo hagas escogerás el # 3 de C3 y terminarás.

Si el usuario ha estado en el cuadrado D2 donde no hay otros puntos tu habría encontrado tu primer partido en decir C2. Al comprobar C1, C2, C3, D1, D3, E1, E2, E3. Una vez que se encontró, entonces tendría que comprobar de nuevo otro radio, que tendría que ser: B0-4, C0, C4, D0, D4, E0, E4, F0-4. etc Usted puede ver que la selección de la red será importante para hacer esto lo más eficiente posible.

También tenga en cuenta esto supone que sus cuadrículas son iguales a diferencia de mi ejemplo dibujado a mano.

Opcion 2:

Si espera un resultado dentro de X km, y desea algo que su DB calculará rápidamente, puede hacer esto:

 LatMin = currentLatCoord-radiusValInDegrees LatMax = currentLatCoord+radiusValInDegrees LonMin = currentLonCoord-radiusValInDegrees LonMax = currentLonCoord+radiusValInDegrees SELECT * From Locations WHERE Lat BETWEEN LatMin AND LatMax AND Lon BETWEEN LonMin AND LonMax 

Ahora esto le da todos los resultados en un cuadrado. Es importante que compruebe que están realmente en el círculo – necesita dejar caer cualquiera en las esquinas, ya que en realidad puede haber coordenadas más cercanas que las del borde del círculo. Por lo tanto, para cada punto, compruebe si está dentro del círculo primero ( ecuación para probar si un punto está dentro de un círculo ) y luego calcule la distancia y mantenga la más cercana. Si no obtienes un resultado, ensancha el círculo.

Una vez más, seleccionar un buen radio dependerá de sus datos.

¿Has consultado este Sitio de cómo contar para la distancia entre dos puntos en la Tierra ?

Pero basta con tener en cuenta que da la distancia basada en la superficie terrestre no basada en el camino real para alcanzar en esa posición. Así que si quieres contar la distancia basada en el Camino Actual para alcanzar esa posición, puedes obtenerla usando Google MAP API.

Google Maps API da la distancia entre dos punto basado en la ruta real.

Espero que esta información hosco ayudarle.

Disfrute de la codificación … 🙂

Distancia entre dos puntos: ((x1 - x2) ^ 2 + (y1 - y2) ^ 2) ^ 0.5 . Sin embargo, la distancia entre estos puntos son rectas. Lo más probable, hay variables como local vs carretera, por no hablar de las calles de un solo sentido y vías navegables, donde es necesario encontrar el puente más cercano. Por lo tanto, sugiero utilizar mapas de Google y Bing api. Son gratuitos para un número limitado de búsquedas.

Hay una solución bastante inteligente en Query para obtener registros basados ​​en Radius en SQLite? basado en la precalculación de algunos valores trigonométricos para cada posición al insertar las filas que luego le permite calcular la distancia en su consulta sólo mediante funciones aritméticas.

Lo he utilizado con mucho éxito en mi propio código

Permítame asegurarme de que esto es correcto: Tienes punto a , y una tabla de puntos a[] . Actualmente, usted hace algo como:

  • bucle sobre b[]
    • obtener distance de b[i] a a
    • si la distance es menor que la distance minimumDistance
      • establecer minimumDistance = distance
      • set closestPoint = i
  • return closestPoint

Si es así, lo encuentras en O(n) tiempo, que realmente no se puede mejorar mucho. Usted tiene que comprobar todos los puntos para ver cuáles son los más cercanos.

Sin embargo, como señala Matthew, puede podar n asignando puntos a una cuadrícula. Esto puede reducir drásticamente la cantidad de puntos necesarios para comparar. El gasto es un poco de tiempo de preprocesamiento, y la lógica un poco más complicado. Si tiene una larga lista de puntos (o la función de distance() tarda mucho tiempo), definitivamente querrá hacer algo como esto.

Depende de cuánto te importe ser correcto cuando cerca de los polos

si la distancia más cercana por pythagorean es bastante buena usted puede utilizar esto en el orderby del sql

p.ej. SELECT * FROM locations ORDERBY (Lat-myLat)*(Lat-myLat) + (Lon-myLon)*(Lon-myLon) LIMIT 1

No es técnicamente la más correcta, pero guarda la obtención de todas las ubicaciones de la base de datos y el bucle sobre ellos, vamos sqlite hacer eso por usted

Puede usar mi curva de hilbert de php class @ phpclasses.org. Utiliza una curva monstruosa y un quadkey para encontrar la distancia más corta. Para buscar la tecla quad puede usar cualquier profundidad.

Aunque esto no es una mejor opción.
Deje que usted está tratando de averiguar la distancia más corta dentro de N millas / km radioso para no fijo de ubicaciones / sus datos de la tabla de ubicación no están cambiando regularmente.
Añadir otra columna Distance_Index (DI) una clave de multi-referencia multi ArrayType. Una vez ejecute un procedimiento y actualice el DI con ID en orden ascendente según la distancia de este DI. Ahora, desde la próxima vez que la distancia de los onwords esté contigo. simplemente haga una consulta a la base de datos y úsela.
Datos de la tabla de ejemplo

Ahora, en su problema no de la ubicación son menos dentro de N, entonces DI no será demasiado largo. Sólo como una opinión.

  • Obtener la dirección de ubicación actual de la aplicación de Android
  • Posicionamiento egnos en un dispositivo android
  • Android: Obtener ubicación reciente solamente, no getLastKnownLocation?
  • Obtención de la ubicación actual de un dispositivo mediante la función {X} api
  • ¿Es posible obtener distancia entre la ubicación actual y una calle, avenida o zona?
  • Obtener ubicación * gruesa * del proveedor de GPS en Android
  • Android: Location.distancePara no funcionar correctamente?
  • Problemas de permiso para la ubicación en android Marshmallow applicaton
  • Usar ubicación simulada sin configurarla en la configuración
  • Cálculo de distancia desde mi ubicación hasta la ubicación de destino en android
  • No puede encontrar la ubicación exacta actual en android
  • FlipAndroid es un fan de Google para Android, Todo sobre Android Phones, Android Wear, Android Dev y Aplicaciones para Android Aplicaciones.