Como eu procuro eficientemente todos os pontos de referência dentro de um intervalo de um determinado ponto de referência?

14

Estou tentando começar com um projeto de pesquisa geográfica que encontrará todos os pontos de referência nos 10 km / milhas (não importante para esta história) de um ponto de referência específico.

Por exemplo, digamos que eu tenha um banco de dados de 1.000.000 de pontos de referência. Para encontrar todos os pontos de referência em um raio de 10 milhas de um ponto de referência com determinadas coordenadas, eu teria que calcular a distância entre um ponto de referência da minha pesquisa e um milhão de pontos de referência.

Existe uma maneira melhor de fazer isso?

A alternativa que eu estava pensando é categorizar marcos como país, região, cidade, vizinhança, negócios, histórico, etc. de tal forma que os negócios possam fazer parte de um bairro ou cidade. A cidade faz parte de uma região, um país, etc. Isso pode restringir uma lista de cálculos, mas ainda parece muito trabalho ser feito para que a pesquisa seja rápida e precisa.

A API do Google Maps pode ajudar?

    
por Dario Granich 05.11.2018 / 13:11
fonte

4 respostas

11

Desde o SQL Server 2008, há um geografia tipo de dados que armazena locais (lat / lon pares) e torna mais fácil para você escrever consultas relacionadas com localização.

Existe uma resposta do StackOverflow que discute isso em profundidade.

Uma consulta básica para encontrar os 7 itens mais próximos :

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);  

Uma consulta básica para encontrar tudo dentro 100m (segunda resposta à pergunta)

-- 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
    
por 05.11.2018 / 13:24
fonte
30

Use um banco de dados com suporte para consultas GIS (sistemas de informações geográficas) . A maioria dos bancos de dados oferece suporte a isso ou possui extensões, mas os detalhes serão específicos do banco de dados (em sua resposta , Flater mostra a sintaxe para o servidor SQL).

Se você precisar implementar essas consultas em seu aplicativo, poderá implementar uma estrutura de dados que permita consultas espaciais, por exemplo, uma Árvore k-d . Isso é como uma árvore de pesquisa binária, exceto que cada nível das partições de árvore em uma dimensão de coordenada diferente. Isso permite restringir a pesquisa a um conjunto menor de candidatos viáveis. Efetivamente, você converte sua pesquisa “10 km de raio” em limites para cada dimensão de coordenada e aperta os limites conforme você recorre à árvore.

    
por 05.11.2018 / 13:32
fonte
11

Sim, há um jeito melhor. Você precisa usar um índice espacial . Esses índices organizam metadados sobre geometrias para filtrar geometrias distantes muito rapidamente, economizando muitos ciclos de CPU evitando os cálculos que você descreve. Você não deve se preocupar em implementá-lo como todos os principais bancos de dados relacionais fornecem um tipo de geometria espacial e índices para acompanhá-los.

  • PostGIS (a extensão GIS para PostgreSQL) usa R-Trees: link (o tipo GiST)
  • SQL Server usa índices de grade: link
  • O Oracle usa o R-Trees: link
  • O MySQL usa o R-Trees: link

O que você quer examinar são consultas "dentro da distância" (consultas para geometrias dentro de uma certa distância de alguma outra geometria). Estes são um problema muito padrão e muito resolvido e são possíveis em todos os bancos de dados acima (e embutidos em vários):

  • PostGIS: ST_DWithin
  • SQL Server: STDistance ( Não está claro que o uso de índice na versão geográfica em 3D desta função é suportado)
  • Oracle: SDO_WITHIN_DISTANCE (isso não diz explicitamente que ele acionará o uso do índice. Eu verificaria o plano de consulta. Talvez seja necessário aplicar um SDO_FILTER para que ele use o índice.
  • MySQL: Ainda entendendo isso.

Solução alternativa para acionar o uso do índice

No pior caso em que você tem problemas para fazer o sistema usar o índice espacial com essas consultas, é possível adicionar um filtro adicional. Você criaria uma caixa delimitadora quadrada com lados de comprimento 2 * (distância de pesquisa) centralizada em seu ponto de pesquisa e compararia as caixas delimitadoras das geometrias da tabela com essa antes de verificar a distância real. Isso é o que o ST_DWithin do PostGIS 'acima faz internamente de qualquer maneira.

Distância em GIS

Enquanto os índices espaciais são fantásticos e absolutamente a solução certa para o seu problema, o cálculo da distância pode ficar logicamente complicado. Em particular, você precisa se preocupar com o que projeção (basicamente todos os parâmetros para o sistema de coordenadas) seus dados são armazenados dentro A maioria das projeções 2D (coisas além de sistemas de coordenadas angulares como as várias projeções lat / long ) distorcer o comprimento de forma significativa. Por exemplo, a projeção do Web Mercator (aquela usada pelo Google, Bing e todos os outros principais fornecedores de mapas de base) expande áreas e distancia cada vez mais à medida que o local se distancia do equador . Eu posso estar errado, já que não sou formalmente educado em GIS, mas o melhor que eu já vi para projeções 2D são alguns específicos que prometem distâncias corretas de um single, ponto constante em todo o mundo. (Não, não é prático usar uma projeção diferente para cada consulta; isso tornaria seus índices inúteis.)

O resultado é que você precisa ter certeza de que sua matemática é precisa. A maneira mais simples de fazer isso a partir de uma perspectiva de desenvolvimento é usar projeções angulares (que são frequentemente chamadas de "geográficas") e funções que suportam a matemática usando um modelo esferóide, mas esses cálculos são um pouco mais caros do que as contrapartes 2D. e alguns DBs podem não suportar indexá-los. Se você conseguir um desempenho aceitável usando-os, provavelmente esse é o caminho a percorrer. Outra opção comum são as projeções regionais (como as zonas UTM) que tornam as distâncias e as áreas muito próximas de serem corretas se os dados estiverem confinados em uma parte específica do mundo. O que é melhor para seu aplicativo dependerá de seus requisitos específicos, mas esteja ciente de que você precisa pensar nisso e talvez aprenda um pouco sobre isso.

Isso se aplica mesmo se você não usar índices espaciais incorporados. Seus dados têm alguma projeção, independentemente de qual tecnologia ou técnica você esteja usando ou usando no futuro, e ela já está afetando atualmente quaisquer consultas e cálculos que você esteja fazendo.

    
por 05.11.2018 / 18:00
fonte
3

Eu concordaria que, se possível, usar suporte específico em um banco de dados seria a maneira mais sensata de fazer isso.

No entanto, se eu tivesse que fazer isso em um banco de dados sem suporte específico, eu começaria consultando um quadrado que encerra a circulação, e. (y > (y1 - rad)) AND (y < (y1 + rad)) AND (x > (x1 - rad)) AND (x < (x1 + rad)). Assumindo que os seus pontos têm uma distribuição praticamente uniforme, a consulta de um quadrado dá-lhe as suas correspondências verdadeiras, mais cerca de 30% de correspondências falsas extras. Você pode então selecionar as correspondências falsas.

    
por 05.11.2018 / 16:58
fonte