Geolocalización en las apps

jrvidal commented 11 years ago

Para implementar geolocalización en las apps, necesitamos una manera sencilla de hacer búsquedas en la BDD WebSQL. Si nos restringimos a España, que está bastante lejos del polo y del meridiano 180, se puede aproximar la distancia por una fórmula sencilla:

d = (dif. latitud)^2 + seno(latitud)^2*(dif. longitud)^2

El error al hacer esto es menor que el 1%, lo cual nos sobra. Para hacer las queries a la BDD, es incluso mejor pedirle un "rectángulo" en lugar de un círculo, es decir, algo así como:

find x 
  where x.lat > poi.lat - dist.lat
  where x.lat < poi.lat + dist.lat
  where x.lon * sin(x.lat) > (poi.lon - dist.lon) * sin(poi.lat)
  where x.lon * sin(x.lat) < (poi.lon + dist.lon) * sin(poi.lat)

Dependiendo de la precisión que queramos, con los resultados de esta query podría utilizarse la fórmula complicada para descartar los resultados de las esquinas del rectángulo, que estarán más lejos de lo deseado.

Para optimizar esta búsqueda, sería conveniente almacenar latitud, longitud y un campo extra de "longitud normalizada" tal que:

x.norm = x.lon * sin(x.lat)

Esto toma algo más de espacio en la BDD, pero acelera la búsqueda.

jrvidal commented 11 years ago

El error al calcular la distancia entre Galicia y Murcia (~900 km) con la fórmula aproximada es de unos 30km (~3%).

jrvidal commented 11 years ago

Hay que considerar implementar Geohashing. Nos permite básicamente hacer lo mismo, pero ocupa menos espacio en el WebSQL.

jrvidal commented 11 years ago

Problemas con GeoHashing:

Necesitamos una implementación de terceros para no embarrarnos. La implementación tendría que tener todos los trucos, porque cerca del meridiano 0º hay una discontinuidad (pura chorra que los datos de testing son en Huesca... :smile: )
El cálculo de distancia no se acelera: que yo sepa, aún hay que convertir de vuelta a coordenadas para hacerlo.
Para filtrar una serie de puntos por distancia, no me parece que ofrezca una ventaja muy superior a filtro que mostré arriba. Hay que calcular una serie de celdas adyacentes y buscar POIs en esas celdas, cuyo número (dependiendo de la precisión) puede ser de decenas.

La ventaja clara de geohashing es el espacio: una string frente a 3 floats. Es un ahorro de unos pocos bytes por entrada en la tabla, que no es importante mientras estemos por debajo de unas 10.000 entradas.

jrvidal commented 11 years ago

Voy a cerrar esto. Si migramos a SQLite (ref #33) el espacio ya no es un problema.

icoloma / appbuilder

Geolocalización en las apps #17