¿Cómo busco eficientemente todos los puntos de referencia dentro de un rango de un punto de referencia determinado?

14

Estoy intentando comenzar con un proyecto de búsqueda geográfica que encontrará todos los puntos de referencia en los 10 km / millas (no es importante para esta historia) de un punto de referencia en particular.

Entonces, por ejemplo, digamos que tengo una base de datos de 1,000,000 de puntos de referencia. Para encontrar todos los puntos de referencia en un rango de 10 millas de un punto de referencia con ciertas coordenadas, tendría que calcular la distancia entre un punto de referencia de mi búsqueda y 1,000,000 de puntos de referencia.

¿Hay una mejor manera de hacerlo?

La alternativa que pensé es clasificar los puntos de referencia como país, región, ciudad, vecindario, negocios, histórico, etc. de tal manera que los negocios puedan ser parte de un vecindario o ciudad. La ciudad es una parte de una región, un país, etc. Esto puede limitar una lista de cálculos, pero todavía parece mucho trabajo por hacer para que la búsqueda sea rápida y precisa.

¿Podría ayudar la API de Google Maps?

    
pregunta Dario Granich 05.11.2018 - 13:11
fuente

4 respuestas

11

Desde SQL Server 2008, hay un geografía que almacena ubicaciones (pares lat / lon) y facilita la escritura de consultas relacionadas con la ubicación.

Hay una respuesta de StackOverflow existente que trata esto en profundidad. a>

"

Una consulta básica para encontrar los 7 elementos más cercanos :

USE AdventureWorks2012  
GO  
DECLARE @g geography = 'POINT(-121.626 47.8315)';  
SELECT TOP(7) SpatialLocation.ToString(), City FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);  

Una consulta básica para encontrar todo dentro 100m (segunda respuesta a la pregunta)

-- Get the center point
DECLARE @g geography
SELECT @g = geo FROM yourTable WHERE PointId = something

-- Get the results, radius 100m
SELECT * FROM yourTable WHERE @g.STDistance(geo) <= 100
    
respondido por el Flater 05.11.2018 - 13:24
fuente
30

Utilice una base de datos con soporte para las consultas GIS (sistemas de información geográfica) . La mayoría de las bases de datos admiten esto directamente o tienen extensiones, pero los detalles serán específicos de la base de datos (en su respuesta , Flater muestra la sintaxis para el servidor SQL).

Si necesita implementar dichas consultas dentro de su aplicación, puede implementar una estructura de datos que permita consultas espaciales, por ejemplo. un árbol k-d . Esto es como un árbol de búsqueda binario, excepto que cada nivel de árbol se divide en una dimensión de coordenadas diferente. Esto le permite restringir la búsqueda a un conjunto más pequeño de candidatos factibles. Efectivamente, traduce su búsqueda "radio de 10 km" en límites para cada dimensión de coordenada y ajusta los límites a medida que retrocede en el árbol.

    
respondido por el amon 05.11.2018 - 13:32
fuente
11

Sí, hay una mejor manera. Debe utilizar un índice espacial . Estos índices organizan metadatos sobre geometrías para filtrar geometrías lejanas muy rápidamente, ahorrando muchos ciclos de CPU al evitar los cálculos que usted describe. No debería molestarse en implementar uno usted mismo, ya que todas las principales bases de datos relacionales proporcionan un tipo de geometría espacial e índices para ir con ellos.

  • PostGIS (la extensión GIS para PostgreSQL) utiliza R-Trees: enlace (The GiST type)
  • SQL Server utiliza índices de cuadrícula: enlace
  • Oracle utiliza R-Trees: enlace
  • MySQL usa R-Trees: enlace

Lo que quieres mirar son las consultas "a distancia" (consultas de geometrías a una cierta distancia de otra geometría). Estos son problemas muy estándar y muy resueltos y son posibles en todas las bases de datos anteriores (y están integradas en varias):

  • PostGIS: ST_DWithin
  • SQL Server: STDistance ( No está claro si el uso del índice en la versión de geografía 3D de esta función es compatible)
  • Oracle: SDO_WITHIN_DISTANCE (Esto no dice explícitamente que activará el uso del índice. Revisaré el plan de consulta. Es posible que deba aplicar un SDO_FILTER para que use el índice.)
  • MySQL: Todavía estoy averiguando esto.

Solución para activar el uso del índice

En el caso peor en el que tiene problemas para que el sistema utilice el índice espacial con estas consultas, puede agregar un filtro adicional. Debería crear un cuadro de límite cuadrado con lados de longitud 2 * (distancia de búsqueda) centrado en su punto de búsqueda y comparar los cuadros de límite de las geometrías de la tabla con ese antes de verificar la distancia real. Eso es lo que PostGIS ' ST_DWithin anterior hace internamente de todos modos.

Distancia en GIS

Si bien los índices espaciales son fantásticos y absolutamente la solución correcta para su problema, el cálculo de la distancia puede complicarse lógicamente. En particular, debe preocuparse por la proyección (básicamente, todos los parámetros para el sistema de coordenadas) en que se almacenan sus datos. La mayoría de las proyecciones 2D (cosas distintas de los sistemas de coordenadas angulares, como las diversas proyecciones de latitud / longitud) ) distorsionar la longitud significativamente. Por ejemplo, la proyección de Web Mercator (la utilizada por Google, Bing y todos los demás proveedores principales de mapas base) expande áreas y distancias cada vez más a medida que la ubicación se aleja del ecuador . Puede que me equivoque, ya que no tengo una educación formal en SIG, pero lo mejor que he visto para proyecciones en 2D son algunas específicas que prometen distancias correctas desde un punto único y constante en todo el mundo. (No, no es práctico usar una proyección diferente para cada consulta; eso haría que sus índices sean inútiles).

La conclusión es que necesita asegurarse de que sus cálculos sean precisos. La forma más sencilla de hacerlo desde una perspectiva de desarrollo es usar proyecciones angulares (a menudo se las denomina "geográficas") y funciones que permiten realizar cálculos matemáticos utilizando un modelo esferoidal, pero estos cálculos son un poco más caros que los equivalentes 2D. y algunas bases de datos pueden no ser compatibles con la indexación. Sin embargo, si puede obtener un rendimiento aceptable usándolos, esa es probablemente la manera de hacerlo. Otra opción común son las proyecciones regionales (como las zonas UTM) que acercan tanto las distancias como las áreas para corregirlas si sus datos se limitan a una parte particular del mundo. Lo mejor para su aplicación dependerá de sus requisitos específicos, pero tenga en cuenta que debe pensar en esto y quizás aprender un poco al respecto.

Esto se aplica incluso si no utiliza índices espaciales integrados. Sus datos tienen cierta proyección, independientemente de la tecnología o técnica que utilice o utilice en el futuro, y ya está afectando a las consultas y cálculos que realice.

    
respondido por el jpmc26 05.11.2018 - 18:00
fuente
3

Estoy de acuerdo en que, si es posible, utilizar la asistencia específica en una base de datos sería la forma más sensata de hacerlo.

Sin embargo, si tuviera que hacer esto en una base de datos sin un soporte específico, empezaría por buscar un cuadrado que encierre la circule, por ejemplo. (y > (y1 - rad)) AND (y < (y1 + rad)) AND (x > (x1 - rad)) AND (x < (x1 + rad)). Asumiendo que sus puntos tienen una distribución más o menos equitativa, la consulta por un cuadrado le proporcionará sus verdaderas coincidencias más un 30% de coincidencias falsas adicionales. A continuación, puede seleccionar las coincidencias falsas.

    
respondido por el Peter Green 05.11.2018 - 16:58
fuente

Lea otras preguntas en las etiquetas