30 de July de 2013

Como implementar backend para app mobile com geolocalização

Neste artigo, vamos discutir como implementar, em um backend, um serviço essencial para aplicativos que precisam mostrar mapas ou listas com pontos de interesse próximos à localização do usuário, como apps de táxi ou de entregas (delivery) em geral.

Motivação

A figura 1 é uma das telas de um aplicativo para chamar táxis. Ela mostra um mapa com a localização dos táxis que estão mais próximos ao usuário. Para fazer isto, o aplicativo precisa se comunicar com um serviço externo que “saiba” onde os pontos de interesse – neste caso, os táxis – estão naquele momento. O aplicativo informa ao serviço a localização atual do usuário, e recebe em resposta a lista de pontos que indicará no mapa.

Figura 1 - Mapa com os táxis mais próximos ao usuário. O retângulo cinza indica a localização atual do usuário, e os círculos em verde e vermelho indicam os táxis mais próximos. A cor verde indica que o táxi está livre, e a vermelha, ocupado.

Figura 1 – Mapa com os táxis mais próximos ao usuário. O retângulo cinza indica a localização atual do usuário, e os círculos em verde e vermelho indicam os táxis mais próximos. A cor verde indica que o táxi está livre, e a vermelha, ocupado.

Este tipo de funcionalidade se aplica a diversos outros contextos. Eis alguns exemplos (e tenho certeza de que você é capaz de pensar em muitos outros):

  • Um aplicativo turístico que mostre os restaurantes mais próximos.
  • Um aplicativo de carona que mostre onde estão, ou quem são, as pessoas mais próximas que solicitam ou oferecem carona.
  • Um aplicativo de paquera que mostre uma lista de pessoas nas proximidades do usuário que também estão procurando um par romântico naquele momento.
  • Um sistema de atendimento técnico que mostre os técnicos que estão próximos aos locais onde um atendimento foi solicitado, para que a central decida quem enviará.

Os serviços do backend

Um backend para esses aplicativos precisa fornecer pelo menos dois serviços importantes:

  1. Rastreamento: recebe as localizações mais recentes das pessoas, veículos ou estabelecimentos envolvidos e armazena em um banco de dados.
  2. Lista: recebe a localização do usuário e fornece a lista de pessoas, veículos ou estabelecimentos mais próximos que atendem aos critérios desejados.

A figura 2 mostra um esquema conceitual para um backend deste tipo. Os veículos ou pessoas enviam periodicamente sua localização para o serviço de rastreamento, que a armazena em um banco de dados. Com as informações armazenadas no banco de dados, o serviço de lista é capaz de identificar quais deles estão mais próximos a uma determinada localização. No exemplo, o serviço informa quais táxis estão mais próximos ao usuário no momento.

Figura 2 - Esquema conceitual de um backend que proporciona os serviços de rastreamento e lista de pontos de interesse próximos ao usuário, e sua interação com o usuário e objetos rastreados.

Figura 2 – Esquema conceitual de um backend que proporciona os serviços de rastreamento e lista de pontos de interesse próximos ao usuário, e sua interação com o usuário e objetos rastreados.

O serviço de Rastreamento

A implementação do serviço de rastreamento, do lado do backend, é relativamente simples. Ele receberá a identificação do veículo ou pessoa sendo rastreada, acompanhada das coordenadas atuais, e armazenará estas coordenadas no banco de dados, substituindo as últimas recebidas. As recomendações óbvias aqui são usar índices de banco de dados, definir a estrutura de forma que apenas uma tabela seja consultada/atualizada em cada chamada e, se possível, particionar essa tabela. Não entraremos em maiores detalhes sobre o serviço de rastreamento neste artigo.

O serviço de Lista

O serviço de lista requer maior atenção, pois tem maior probabilidade de não escalar bem, dependendo de como seja implementado. As duas razões mais prováveis para este serviço não escalar bem são o desempenho das consultas feitas ao banco de dados e a necessidade de chamar uma API externa.

Para determinar que táxis estão mais próximos do usuário, a distância entre cada táxi e o usuário deverá ser calculada, e o resultado ordenado. Existe uma diferença entre a distância “direta” (em linha reta, se a Terra fosse plana) e a distância considerando as vias existentes e o tráfego entre dois locais. Nos casos em que esta última seja necessária, usaremos a Google Distance Matrix API. Em ambos os casos, faremos alguns cálculos envolvendo distâncias, latitudes e longitudes.

Google Distance Matrix API

O Google fornece um serviço chamado Google Distance Matrix API (referência [1]). Ele recebe uma lista de geolocalizações de origem e de destino e o modo de viagem desejado (driving, walking ou bicycling – dirigindo, andando ou pedalando) e retorna as distâncias e duração da viagem para cada par origem/destino.

A decisão por usar este serviço não é tão óbvia quanto parece. Há limitações de volume de uso e de quantidade de pares origem/destino por chamada, tanto em sua cota de uso gratuito quanto na modalidade paga. Na verdade, é compreensível que o Google imponha limites de uso, dada a complexidade dos cálculos e o potencial para abuso do serviço.

Restringindo a Lista

Não é viável enviar a posição do usuário e de todos os táxis existentes no banco para a Google Distance Matrix API a cada consulta ao serviço Lista. O backend deve ser capaz de fazer uma primeira filtragem, e enviar a menor quantidade possível de táxis para a API. Em outras palavras, a implementação do serviço Lista deve minimizar – ou se possível eliminar – as consultas à Google Distance Matrix API.

Como temos as latitudes e longitudes armazenadas em campos de uma tabela no banco de dados, a maneira mais eficiente de limitar a lista seria usando índices de banco que incluam esses campos.

Nosso objetivo é selecionar, por exemplo, os táxis que estejam a no máximo 1 km do usuário, em uma medida “direta”, e depois submeter apenas esses táxis para a Google Distance Matrix API, para obter suas distâncias em modo “dirigindo”. Na figura 3, estes seriam os táxis dentro da região demarcada pelo círculo azul.

Figura 3 - Área em que os táxis que estão a menos de 1 km do usuário estariam posicionados. Os táxis fora do círculo azul, a princípio, serão desconsiderados.

Figura 3 – Área em que os táxis que estão a menos de 1 km do usuário estariam posicionados. Os táxis fora do círculo azul, a princípio, serão desconsiderados.

É possível que o táxi mais próximo, quando em distância “direta”, não seja o mais próximo quando considerado o percurso dirigindo. A ordenação dos resultados retornados pela API tende a diminuir este efeito.

A distância “direta” entre dois pontos é a linha de menor comprimento, sobre a superfície da Terra, que os liga. É o equivalente à distância em linha reta entre eles, se a Terra fosse plana.

Existe uma fórmula para calcular esta distância, e portanto o backend pode fazê-lo sem a ajuda de uma API externa. Supondo que esta fórmula fosse implementada como uma função DISTANCE_BETWEEN() do banco de dados, um comando SQL para obter a lista seria algo como:

select * from posicao_taxi p
where distance_between(p.lat, p.lng, :lat_usuario, :lng_usuario) <= :raio;

Não podemos usar um índice de banco com a distância, já que ela depende da posição do usuário, informada no momento da consulta. Então, da forma como mostrado acima, este comando iria forçar o banco de dados a calcular a distância entre a localização do usuário e todos os táxis da tabela, resultando em um full scan da mesma, o que é muito ineficiente. Podemos melhorar esta consulta definindo um índice por latitude e longitude e restringindo a mesma aos extremos de latitude e longitude para os táxis que se encontram no raio desejado.

Por exemplo:

select * from posicao_taxi p
where p.lat between :lat_min and :lat_max
and p.lng between :lng_min and :lng_max
and distance_between(p.lat, p.lng, :lat_usuario, :lng_usuario) <= :raio;

Na consulta, LAT_MIN e LAT_MAX são a menor e a maior latitudes que um táxi que está dentro de um raio de RAIO km do usuário pode ter. Analogamente para LNG_MIN e LNG_MAX em relação à longitude.

Dependendo do banco de dados utilizado e da estrutura do banco, pode ser necessário colocar a condição do cálculo de distância em uma subquery ou na cláusula HAVING do comando, de forma que o índice baseado nos campos de latitude e longitude seja utilizado pelo otimizador de consultas do banco. Podemos verificar o que o otimizador irá fazer, usando um comando como o EXPLAIN, no caso do MySQL. No nosso exemplo, o otimizador do MySQL identificou corretamente o índice a ser usado apenas com as condições na cláusula WHERE, não foi necessário usar a cláusula HAVING ou uma subquery. Para exemplos do uso de subquery e da cláusula HAVING neste tipo de consulta, veja a referência [2].

De qualquer forma, um ‘hint’ para forçar o uso do índice também é um bom recurso.

Precisamos agora determinar os valores de LAT_MIN, LAT_MAX, LNG_MIN e LNG_MAX. Se o sistema de coordenadas fosse o cartesiano, em um plano, estes pontos seriam os mostrados na figura 4-A. Porém, trabalhando com o sistema de coordenadas esféricas, uma boa aproximação para garantir incluir todos os táxis dentro do raio desejado é calcular os paralelos e meridianos que são tangentes ao círculo demarcado na figura 3. Isto corresponderia, no hemisfério Sul, aos pontos mostrados na figura 4-B. As linhas horizontais, que são os paralelos, mantém a mesma distância entre si (como o nome sugere); já a distância entre dois meridianos diminui à medida que eles se aproximam dos pólos, onde todos se encontram.

Figura 4-A - Pontos de menor e maior latitude e longitude se o sistema de coordenadas fosse o plano cartesiano.

Figura 4-A – Pontos de menor e maior latitude e longitude se o sistema de coordenadas fosse o plano cartesiano.

Figura 4-B - Pontos de menor e maior latitude e longitude no sistema de coordenadas esféricas, para o hemisfério Sul.

Figura 4-B – Pontos de menor e maior latitude e longitude no sistema de coordenadas esféricas, para o hemisfério Sul.

Ao restringir as latitudes e longitudes desta forma, serão incluídos todos os táxis dentro do quadrilátero em vermelho, que são um superconjunto dos táxis dentro do círculo. A condição por distância irá excluir os que estiverem fora do círculo.

Calculando a distância, latitudes e longitudes mínimas e máximas

A Geometria Esférica fornece as fórmulas que precisaremos.

A Terra, que é um elipsóide, é modelada para efeito de uso destas fórmulas como uma esfera de raio 6.371 km. Esta aproximação é precisa o suficiente para os propósitos deste tipo de aplicação, segundo diversas fontes consultadas.

Apresentaremos as fórmulas implementadas como funções do banco de dados MySQL. Nas referências [2], [3] e [4], implementações em outras linguagens podem ser encontradas.

Não usaremos a extensão Geoespacial do MySQL. Segundo a documentação da mesma, só é possível criar índices espaciais em tabelas MyISAM, e as funções disponíveis usam geometria plana ao invés de esférica.

DISTANCE_BETWEEN(FROM_LAT, FROM_LNG, TO_LAT, TO_LNG)

Distância entre as coordenadas (from_lat, from_lng) e (to_lat, to_lng), em quilômetros, com 3 casas decimais.

create function `distance_between`(from_lat decimal(18, 12), from_lng decimal(18, 12), to_lat decimal(18, 12), to_lng decimal(18, 12)) returns decimal(11,3)
return 6371 * 2 * atan2(sqrt(pow(sin(radians(to_lat - from_lat)/2), 2) + pow(sin(radians(to_lng - from_lng)/2), 2) * cos(radians(from_lat)) * cos(radians(to_lat))), sqrt(1 - pow(sin(radians(to_lat - from_lat)/2), 2) + pow(sin(radians(to_lng - from_lng)/2), 2) * cos(radians(from_lat)) * cos(radians(to_lat))));

Esta fórmula é equivalente à conhecida fórmula do semiverseno (“haversine formula”), exceto que está expressa em função de um arco-tangente e não de um arco-seno, para que seja possível usar a função atan2(), mais bem comportada do que a função asin() quanto a lidar corretamente com o numerador e o denominador da fórmula.

Nas referências [5], [6] e [7] há mais informações sobre a “haversine formula”.

MIN_LAT(FROM_LAT, DISTANCE), MAX_LAT(FROM_LAT, DISTANCE):

Latitudes mínima e máxima dos pontos que estão a uma determinada distância, em quilômetros, de uma dada latitude.

create function `min_lat`(from_lat decimal(18, 12),
distance decimal(11, 3)) returns decimal(18,12)
return from_lat - degrees(distance/6371.0);
create function `max_lat`(from_lat decimal(18, 12),
distance decimal(11, 3)) returns decimal(18,12)
return from_lat + degrees(distance/6371.0);

MIN_LNG(FROM_LAT, FROM_LNG, DISTANCE), MAX_LNG(FROM_LAT, FROM_LNG, DISTANCE):

Longitudes mínima e máxima dos pontos que estão a uma determinada distância, em quilômetros, de um dado ponto.

create function `min_lng`(from_lat decimal(18, 12), from_lng decimal(18,12),
distance decimal(11, 3)) returns decimal(18,12)
return from_lng - degrees(asin(distance/6371.0)/cos(radians(from_lat)));
create function `max_lng`(from_lat decimal(18, 12), from_lng decimal(18,12),
distance decimal(11, 3)) returns decimal(18,12)
return from_lng + degrees(asin(distance/6371.0)/cos(radians(from_lat)));

Nota: O que as fórmulas acima fazem é calcular um “delta” e somá-lo ou subtraí-lo da coordenada correspondente à posição do usuário. No caso das latitudes, como as linhas que definem uma mesma latitude são paralelas entre si (e paralelas à Linha do Equador), a longitude do ponto de origem não faz diferença.

Um ponto sobre o Meridiano de Greenwich estará à mesma distância do Equador do que um ponto de mesma latitude sobre o meridiano de 30°, por exemplo.

É por isto que precisamos apenas da latitude do ponto de origem para calcular as latitudes extremas.

Para as longitudes, a latitude do ponto de origem faz diferença, pois as linhas de mesma longitude, que são os meridianos, não são paralelas entre si; então a distância entre um ponto e um determinado meridiano depende da latitude em que o ponto está. Um ponto sobre a linha do Equador estará mais distante do Meridiano de Greenwich do que um ponto de mesma longitude sobre o Trópico de Capricórnio, por exemplo.

É por isto que precisamos da latitude e da longitude do ponto de origem para calcular as longitudes extremas.

Exemplo de cálculo

A referência [8] é um site que permite o envio de uma lista de coordenadas para que sejam plotadas, e calcula a distância “direta” total do “caminho” formado por elas. É uma boa forma de conferir os cálculos que apresentaremos a seguir.

Vejamos um exemplo numérico. Suponha que o usuário esteja próximo ao estádio do Maracanã, nas coordenadas (-22.913488, -43.227632). sagerainaos4.blogspot.com . Para obter a lista dos táxis que estão a 1 km dele, o serviço Lista, após receber a localização do usuário enviada pelo aplicativo que está rodando em seu aparelho celular, irá:

  1. Calcular os pontos  de latitudes e longitudes mínimas e máximas;
  2. Usar estes valores e a fórmula da distância para selecionar a lista do banco;
  3. (opcional) Passar a lista de coordenadas dos táxis para a Google Distance Matrix API para obter as distâncias e tempos no modo “driving”;
  4. Retornar a lista para o aplicativo.

Cada um dos passos é detalhado a seguir.

1. Calcular os pontos de latitudes e longitudes mínimas e máximas.

Definindo a localização do usuário como (@lat_u, @lng_u) e o raio do círculo como @raio:

set @lat_u = -22.913488;
set @lng_u = -43.227632;
set @raio = 1.0;
select min_lat(@lat_u, @raio),
min_lng(@lat_u, @lng_u, @raio),
max_lat(@lat_u,1),
max_lng(@lat_u, @lng_u, @raio)
from dual
into @lat_min, @lng_min, @lat_max, @lng_max;

Os resultados retornados nas variáveis são:

@lat_min @lng_min @lat_max @lng_max
-22.922481216059 -43.237395627034 -22.904494783941 -43.217868372966

Se houver chance de que algum destes valores esteja fora da faixa de latitudes e longitudes possíveis (±90.0 para latitude e ±180.0 para longitude), um tratamento especial deve ser dado para obter os limites corretos. Veja a seção 3.4 da referência [2] para uma abordagem mais detalhada do assunto.

A figura 5, traçada com o Google Maps (referência [9]), mostra a localização do usuário e o quadrilátero formado pelos pontos de mínimos e máximos.

Figura 5 - Quadrilátero formado pelos pontos de mínimas e máximas latitudes e longitudes calculadas para a posição do usuário no exemplo, a uma distância de 1 km.

Figura 5 – Quadrilátero formado pelos pontos de mínimas e máximas latitudes e longitudes calculadas para a posição do usuário no exemplo, a uma distância de 1 km.

2. Usar os pontos de latitude e longitudes extremas e a distância para selecionar a lista do banco

Supondo que as coordenadas de cada táxi estão armazenadas nos campos lat e lng da tabela posicao_taxi:

select * from posicao_taxi p
where p.lat between @lat_min and @lat_max
and p.lng between @lng_min and @lng_max
and distance_between(p.lat, p.lng, @lat_u, @lng_u) <= @raio
limit 10;

A lista resultante do comando acima trará os 10 (ou menos) táxis mais próximos, que estão no entorno do usuário, a uma distância de até 1 km. No nosso banco de dados de exemplo, 5 coordenadas foram retornadas:

-22.922178000,-43.226143000
-22.920178000,-43.228143000
-22.916178000,-43.234143000
-22.910719000,-43.225563000
-22.905178000,-43.227143000

refazendo a consulta sem a restrição de distância, ou seja,

select * from posicao_taxi p
where p.lat between @lat_min and @lat_max
and p.lng between @lng_min and @lng_max
limit 10;

obtemos um total de 8 pontos: os 5 da primeira consulta e mais os 3 listados abaixo, que ainda estão dentro dos limites de latitude e longitude, porém a uma distância maior do que 1 km:

-22.920719000,-43.220563000
-22.918719000,-43.236563000
-22.906178000,-43.220143000

A figura 6 mostra o círculo de 1 km em torno do usuário, os táxis dentro da distância de 1 km e os táxis fora, representados pelos ícones vermelhos de alerta.

Figura 6 - O círculo de 1 km de distância do usuário e os táxis. Os ícones de alerta em vermelho são os 3 táxis fora do raio de 1 km, retornados pela consulta sem restrição de distância.

Figura 6 – O círculo de 1 km de distância do usuário e os táxis. Os ícones de alerta em vermelho são os 3 táxis fora do raio de 1 km, retornados pela consulta sem restrição de distância.

2.1) Ordenando e selecionando a distância

Introduzir uma ordenação por distância representará trabalho extra para o banco de dados. Vejamos o resultado do comando EXPLAIN para a query :

explain select * from posicao_taxi p
where p.lat between @lat_min and @lat_max
and p.lng between @lng_min and @lng_max
and distance_between(p.lat, p.lng, @lat_u, @lng_u) <= @raio
order by distance_between(p.lat, p.lng, @lat_u, @lng_u)
limit 10;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE P range lat lat 14 NULL 83 Using where; Using temporary; Using filesort

Using temporary e Using filesort, na coluna Extra, significam que será necessária uma passada extra pelos dados e a criação de uma tabela temporária para resolver a consulta.

Então, se a ordenação não for absolutamente necessária, não deve ser feita.

Já selecionar a distância junto com os demais campos parece não impor penalidade ao banco:

explain select p.*, distance_between(p.lat, p.lng, @lat_u, @lng_u) from posicao_taxi p
where p.lat between @lat_min and @lat_max
and p.lng between @lng_min and @lng_max
and distance_between(p.lat, p.lng, @lat_u, @lng_u) <= @raio
limit 10;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE P range lat lat 14 NULL 83 Using where

3. (opcional) Passar a lista de coordenadas para a Google Distance Matrix API

Se o objetivo for apenas exibir o mapa com os táxis, não é necessário chamar a Google Distance Matrix API.

Porém, se for necessário, por exemplo, informar o tempo que cada táxi levará para chegar, ou a que distância no modo “dirigindo” cada táxi está do usuário, então será necessário chamar a API.

A lista de coordenadas dos táxis obtidas no passo anterior e a posição do usuário serão passadas à Google Distance Matrix API, no modo “driving”.

As coordenadas dos táxis serão as origens e a localização do usuário, o único destino. A API retornará a distância “dirigindo” e o tempo que cada táxi leva para chegar até o usuário.

Para detalhes de como realizar a chamada à API, veja a documentação da mesma (referência [1]).

Nota: Como se trata de uma chamada a uma API externa, é recomendado que ela ocorra de forma assíncrona – ou seja, que a resposta do serviço Lista seja na forma de um callback, ao invés de aguardar o retorno da chamada à API para concluir o processamento e responder ao aplicativo. Dependendo da tecnologia empregada pelo backend, há diversas maneiras de se fazer isto, mas a maioria envolve sinalizar que a resposta está disponível e entregar a resposta. Para sinalizar que a resposta está disponível, podem ser usadas notificações push da própria plataforma móvel, como o APNS da Apple (referência [10]) ou o GCM do Google (referência [11]), um serviço como o Pusher (referência [12]), ou mesmo um agendamento no aplicativo que consulte a intervalos regulares o serviço que retorna a resposta. Para entregar a resposta, um serviço dedicado a isto pode ser implementado.

4. Retornar a lista para o aplicativo

Se uma API externa tiver sido chamada, é possível que um mecanismo de callback, notificações ou mesmo um pulling a intervalo regulares tenham sido necessários, conforme comentamos na seção anterior. Se nenhuma API externa for chamada, o serviço pode retornar diretamente o resultado ao aplicativo, na forma das coordenadas e informações adicionais necessárias para cada item.

Uma alternativa: backend com Parse

O Parse (referência [13]) é um site que oferece algo como “backend as a service” para aplicativos móveis. Ele conta com um tipo de dados chamado GeoPoint, que armazena pontos em forma de latitudes e longitudes, e pode executar consultas de distâncias com esses pontos.

Usando sua API REST, a consulta anterior ficaria algo como (adaptado do exemplo contido na documentação da API, usando o utilitário curl de linha de comandos):

curl -X GET \
-H "X-Parse-Application-Id: ${APPLICATION_ID}" \
-H "X-Parse-REST-API-Key: ${REST_API_KEY}" \
-G \
--data-urlencode 'limit=10' \
--data-urlencode 'where={
"location": {
"$nearSphere": {
"__type": "GeoPoint",
"latitude": -22.913488,
"longitude": -43.227632
},
"$maxDistanceInKilometers": 1.0
}
}' \
https://api.parse.com/1/classes/PlaceObject

O resultado seria uma lista ordenada por distância, trazendo as latitudes e longitudes de cada táxi. Estes dados podem ser passados à Google Distance Matrix API, como no passo 3 da seção anterior.

Referências:

  1. https://developers.google.com/maps/documentation/distancematrix/
  2. http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates
  3. http://www.movable-type.co.uk/scripts/latlong.html
  4. http://www.movable-type.co.uk/scripts/latlong-db.html
  5. http://en.wikipedia.org/wiki/Great-circle_distance
  6. http://en.wikipedia.org/wiki/Haversine_formula
  7. http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL
  8. http://www.daftlogic.com/projects-google-maps-distance-calculator.htm
  9. http://maps.google.com
  10. https://developer.apple.com/notifications/
  11. http://developer.android.com/google/gcm/index.html
  12. http://pusher.com
  13. http://www.parse.com
5 comments
ReginaldoRigo
ReginaldoRigo

Muito bom. Estou desenvolvendo algo nesse sentido e só ajudou.

wagnerps
wagnerps

Ótimo artigo. Parabéns.

pedroyusim
pedroyusim

Artigo de ótima qualidade. Parabéns.