Quiero crear una gran base de datos de coordenadas GPS que se pueda consultar diciendo "Devuelva todas las coordenadas que están dentro de 'n' metros de [esta coordenada]".Almacenar y consultar coordenadas de GPS con eficacia
Necesito que sea lo más eficiente posible, por lo que recorrer todas las coordenadas de la base de datos y calcular si una coordenada está dentro de 'n' metros no sería una solución deseada.
¿Existe una solución más fácil?
Gracias
Hay apoyo en SQL Server 2008 para almacenar spatial data. Nunca he trabajado con él, pero sí sé que puedes crear consultas del tipo que quieras.
Muchos sistemas de bases de datos tienen una función para trabajar con datos geoespaciales.
Aquí es comparsion funciones geoespaciales entre SQL Server 2008, PosGIS y MySQL http://www.bostongis.com/PrinterFriendly.aspx?content_name=sqlserver2008_postgis_mysql_compare
Si usted puede tener su opción de DB, recomiendo lo mismo que rwwilden y utilizar SQL 2008 con sus capacidades de datos espaciales. Si no puede usar esa solución o una que incluya consultas espaciales, puede echar un vistazo al documento de Microsoft en Hierarchical Triangular Mesh e implementar esas cosas. El SDK para MSSQL '05 también viene con una solución completa para HTM out-of-the-box, por lo que puede tomar eso y convertirlo a cualquier plataforma que esté usando.
EDIT:
Aquí está una más detalle document explicar HTM y aplicación. Por supuesto, puede convertir a su base de datos de su elección. Puede encontrar el código fuente para una implementación HTM completa en el SDK para 2005.
Las bases de datos GIS (MS PostgreSQL etc.) realmente implementan alguna estructura de datos para búsquedas de regiones bidimensionales o tridimensionales (spatial indices). La estructura más simple es el índice de la grilla, luego los diferentes árboles de búsqueda (kd-tree, quad-tree) con R-tree como el más utilizado (un B-tree generalizado para más dimensiones). Estos métodos parecen adecuados.
Un índice de cuadrícula básico (dividir el espacio en cuadrículas, y buscar solo en las celdas cercanas) se puede implementar fácilmente y puede reducir el tiempo de búsqueda a logarítmico. Los árboles de búsqueda son un poco más difíciles de implementar, pero hay muchas implementaciones de código abierto para muchos lenguajes de programación. Sin embargo, en la mayoría de los casos, la indexación de la grilla es lo suficientemente eficiente.
Normalmente hago este tipo de consulta usando lat/lon. Con la geometría esférica, puede colocar un cuadro delimitador alrededor de un punto específico. Por ejemplo, supongamos que tiene un punto (X, Y) que quiere que todas las coordenadas estén dentro de 1 milla (la conversión a metros lo dejo como ejercicio para el lector). Puede determinar un cuadro delimitador de (X-1, Y-1), (X + 1, Y + 1). A continuación, consulta su base de datos de puntos utilizando el operador BETWEEN (SELECCIONE foo FROM bar WHERE LAT ENTRE X-1 Y X + 1 Y LON ENTRE Y-1 E Y + 1). A continuación, realice su cálculo de distancia detallada para "redondear las esquinas" de su cuadro delimitador.
La advertencia es que las líneas de longitud están más juntas en la parte superior de la esfera, por lo que obtendrá resultados asimétricos cuanto más lejos se encuentre del ecuador. Pero aún sirve para filtrar rápidamente sus conjuntos de resultados.
Google "Great Circle Distance" para los cálculos.
EDIT: Hay 0.167469 grados de longitud por milla (en realidad va de 0.167469 a 0.014564) y 0.014483 grados de latitud por milla. Por lo que su cuadro delimitador es (lat - (miles * 0.014483), lon - (miles * 0.167469)), (lat + (miles * 0.014483), lon + (miles * 0.167469))
seguimiento a Erich - si usted tiene sus PostGIS uso elección (PostgreSQL) es de código libre y abierto, hace las consultas que está describiendo muy rápidamente, funciona en casi todas las plataformas, y se me mencionar que es gratis?
Si se quiere evitar una extensión de SIG, que adapta las funciones de this post a postgres sql:
create or replace function change_in_lat(miles numeric)
returns double precision as $$
with v as (select
3960.0 as earth_radius,
180/pi() as radians_to_degrees
) select (miles/earth_radius) * radians_to_degrees from v;
$$ language sql
returns null on null input;
create or replace function change_in_long(lat numeric, miles numeric)
returns double precision as $$
with v as (select
3960.0 as earth_radius,
pi()/180 as degrees_to_radians,
180/pi() as radians_to_degrees
) select (
miles/(earth_radius * cos(lat * degrees_to_radians))
) * radians_to_degrees from v;
$$ language sql
returns null on null input;
mediante los que se pueden hacer algunas cuadrados que rodean consultas:
--find all "a"s within 25 miles of any "b"
select * from a join b on (
a.gpslat between
b.gpslat - change_in_lat(25) and b.gpslat + change_in_lat(25)
and a.gpslong between
b.gpslong - change_in_long(b.gpslat::numeric, 25)
and b.gpslong + change_in_long(b.gpslat::numeric, 25)
);
si se quiere lo usé con la frecuencia suficiente. Estoy seguro de que sería fácil convertir las declaraciones entre en una sola función. Sin embargo, nunca realicé consultas reales "dentro del radio" con esto.
Para algo más complicado, es probable que desee una extensión GIS como han dicho otras respuestas. PostGIS es bueno, pero encontré que muchas de las funciones específicas de gis pueden ser difíciles de entender, y a menos que utilice índices de cuadro delimitador, sus consultas espaciales pueden demorar un día si su conjunto de datos es lo suficientemente grande. Pero la compensación en complejidad definitivamente vale la pena por todas las cosas sofisticadas, como la salida de datos en formato Geojson, etc.