Mais de uma vez, tive que implementar a função de calcular a distância de um determinado ponto geográfico até uma área do mapa - por exemplo, até o anel viário de Moscou. Como resultado, encontrei duas maneiras de resolver o problema que apresentava bons resultados e agora as usamos regularmente na produção. Vou descrevê-los na primeira parte do artigo. E no segundo, mostrarei como você pode armazenar em cache os dados geográficos para usar menos o geocoder.
Parte I Duas maneiras de encontrar a distância de um ponto a uma área em um mapa
Se seu aplicativo móvel é realmente móvel, ele funciona com as coordenadas do dispositivo. A localização do usuário (e dispositivo) afeta vários indicadores de negócios do aplicativo, como custo de entrega, fator de complexidade, etc.
Abaixo, mostrarei exemplos de implementação de algoritmos em python, usando as bibliotecas bem elaboradas e bem torneadas.
Para geocodificação, usamos o Google Maps. Adapta-se à funcionalidade e ao custo de uso. No momento da redação deste artigo, o Google permite que você faça as primeiras 20.000 solicitações de geocodificação por mês gratuitamente.
Método 1. Calculamos a rota com base nos vértices do polígono
Suponha que precisamos encontrar a distância de um ponto em algum lugar da região de Moscou até o anel viário de Moscou. É necessário um caminho real, não geométrico. Portanto, primeiro construímos um aterro a partir dos pontos de saída do anel viário de Moscou, e eles não coincidem com os topos dos contornos da estrada no mapa.
exit_coordinates: List[Tuple[float, float]] latitude: float longitude: float
Para trabalhar com geometria, usamos a biblioteca
bem torneada. Com sua ajuda, é fácil determinar se o ponto de interesse para nós está dentro do polígono ou não. Se for, a distância é obviamente 0.
from shapely.geometry import Polygon, Point polygon = Polygon(exit_coordinates) polygon.contains(Point(latitude,longitude))
Estamos interessados no caso em que o ponto está fora do polígono. A tarefa de encontrar os objetos mais próximos (saídas do MKAD) até o ponto de partida é bastante típica em matemática. Geralmente é resolvido usando uma árvore KD. Então vamos lá. Em python, a árvore é implementada na biblioteca
scipy. Vamos encontrar os picos mais próximos das saídas do anel viário de Moscou até o nosso ponto.
from scipy.spatial import KDTree kd_tree = KDTree(exits_coordinates) dists, indexes = kd_tree.query((latitude, longitude), k=3) nearest_coordinates = list() for _, index in zip(dists, indexes): nearest_coordinates.append(exits_coordinates[index])
O número
k - o número de picos - não deve ser muito pequeno, porque a saída mais próxima do anel viário de Moscou pode estar temporariamente bloqueada. Ou pode estar em algum lugar além do rio e não ter um caminho direto para o nosso ponto.
K muito grande também
é inútil para nós, porque uma saída adequada está localizada em vários picos próximos. Agora vamos ao serviço do Google Maps. Ele já possui uma funcionalidade para encontrar distâncias de uma matriz de pontos para um ponto específico - a API Matriz de Distância.
Atualização: o serviço da API Matriz de distância fatura a rota para cada pico mais próximo separadamente. Assim, esse método é mais caro que o segundo, descrito abaixo. Obrigado
sovetnikov import googlemaps gmaps_client = googlemaps.Client(key=settings.GOOGLE_MAPS_API_KEY) gmaps_client.distance_matrix( origins=nearest_coordinates, destinations=(latitude, longitude), mode='driving', )
Só podemos analisar a resposta. Geralmente, possui várias rotas, e a primeira nem sempre é a mais curta. Portanto, escolhemos o valor apropriado.
Método 2. Calculamos a rota do centro do aterro
Agora, além dos vértices do polígono, definimos algum ponto dentro dele, a partir do qual construiremos todas as rotas do Google Maps. Usaremos a API de rotas, que criará rotas para nós e escolheremos a menor delas.
start_point: Tuple[float, float], destination: Tuple[float, float] polygon: shapely.geometry.Polygon gmaps_client = googlemaps.Client(key=settings.GOOGLE_MAPS_API_KEY) driving_path = gmaps_client.directions(start_point, destination)
Começamos iterativamente do final para adicionar os comprimentos dos segmentos do caminho até que a coordenada do início do segmento esteja dentro do polígono (a análise é omitida):
for step in reversed(driving_path): start_point = step['start_location']['lat'], step['start_location']['lng'] if is_inside_polygon(start_point, self.polygon): end_point = step['end_location']['lat'], step['end_location']['lng'] distance += get_part_outside_polygon( get_line(start_point, end_point), polygon ) * step['distance']['value'] break distance += step['distance']['value']
Só podemos adicionar parte do segmento fora do polígono. Para fazer isso, usando a biblioteca bem torneada, construímos uma linha geométrica entre as coordenadas do início e do final do caminho e descobrimos quanto do seu comprimento está fora do polígono. A mesma porcentagem do comprimento é calculada para o segmento obtido do caminho.
Um caminho é uma rota de terreno em estradas reais com curvatura natural. Se for uma linha reta longa (avenida ou rodovia), nossa aproximação nos permitirá calcular a rota exatamente em termos percentuais.
Se a estrada que cruza o aterro for suficientemente curva, essa aproximação estará incorreta. Mas as partes curvas na rota do Google Maps são geralmente curtas e os erros no cálculo não afetam o resultado.
from shapely.geometry import LineString, Polygon line = LineString(point1, point2) part_outside_len = float(line.difference(polygon).length) / float(line.length)
Para ser sincero, não comparei esses dois métodos. Eu os uso há mais de um ano, ambos funcionam sem falhas. Decidi não pintar sua implementação em detalhes. Em vez disso, ele abriu o acesso à sua
biblioteca geográfica. O Liba também pode usar geocodificação regular, inclusive com armazenamento em cache eficiente. Problemas e solicitações pull são bem-vindos!
Parte Dois Salvar solicitações de geocodificação reversa
Muitas vezes, precisamos determinar os endereços dos pontos que estão próximos e correspondem a um objeto no mundo real. A cada vez, não é legal fazer uma solicitação para um sistema de geocodificação externo, e aqui surge a questão do cache razoavelmente.
Normalmente, o cliente envia as coordenadas com precisão excessiva, por exemplo, 59.80447691, 30.39570337. Mas quantos sinais na parte fracionária serão significativos para nós?
Para os preguiçosos e com pressa, a resposta é quatro. Para todos os outros, veja a explicação abaixo.
Primeiro, um pouco de geografia.
- O equador tem 40.075.696 km de comprimento e é latitude zero.
- Meridianos são linhas de longitude, perpendiculares às linhas de latitude. O comprimento de qualquer meridiano é 40.008,55 km
- Grau de latitude - 40.008,55 km / 360 = 111,134861111 km. Assim, um centésimo dá uma mudança de cerca de um quilômetro e um dez milésimo dá uma mudança de 10 metros.
- A circunferência da linha de latitude diminui do equador e é multiplicada pelo cosseno do ângulo de latitude, portanto, para 60 graus de latitude (latitude de São Petersburgo), o comprimento é inferior a exatamente 2 vezes menos. Então o grau de longitude é 40.075.696 * 0,5 / 360 = 55.66066888 km, ou um décimo milésimo é de 5 metros.
Um erro de 1/10000 graus fornece um retângulo de erro de 5 a 10 por 10 metros. Isso nos permitirá "entrar" exatamente no edifício, como o prédio é muito maior que o ponto. E se, devido a um erro, o ponto não cair dentro do prédio, o Google ainda determinará o mais próximo.
Arredondar até três caracteres é arriscado, a precisão já é significativamente reduzida. E até cinco - não faz sentido, porque a precisão dos transmissores GPS não excede apenas alguns metros.
Portanto, se no cache houver um valor com a chave “endereço: 59.8045,30.3957”, todas as coordenadas, quando arredondadas para 4 caracteres, a mesma chave é obtida, corresponderão a um endereço geocodificado. Fazemos menos solicitações - trabalhamos mais rápido e pagamos menos pelo uso do serviço de geocodificação. Lucro!