chester's blog

technology, travel, comics, books, math, web, software and random thoughts

cruzalinhas

04 Jun 2010

O site da SPTrans oferece várias informações sobre as linhas de ônibus, trem e metrô que operam na cidade de São Paulo. A navegação, entretanto, deixa um pouco a desejar – razão que leva as pessoas a alternativas como o Tô a Pé e o eficiente sistema de rotas do Google Maps.

Este último resolve bem a minha vida, mas às vezes tudo o que eu quero é saber quais ônibus passam por um determinado local. Ou ainda: quais, dentre eles, passam por um segundo local, e quais passam entre este e um terceiro, i.e., quais minhas opções para ir do ponto A ao ponto B, e dele ao ponto C, e por aí em diante.

Misturando essa demanda com um desejo de colocar as informações de itinerário do transporte público de São Paulo nas mãos da população, desenvolvi o cruzalinhas. A aplicação ainda precisa de muitas melhorias (eu diria que é “beta”, mas o que não é?) mas já permite responder às perguntas acima.

Como de costume, o código-fonte é livre (licença MIT), e esse post vai falar um pouco sobre o funcionamento do mesmo.

cruzalinhas

O back-end da aplicação é escrito em Python e hospedado no Google App Engine. Ele disponibiliza um par de chamadas AJAX/JSON para o front-end: uma página HTML que usa o JQuery para acessar tanto esse back-end quanto a API do Google Maps (usada para desenhar os mapas/trajetos e buscar endereços).

Obter os dados de itinerário não foi trivial, mas o principal desafio mesmo era fazer buscas geográficas. Explico: eu tenho, para cada linha, os pontos (latitude e longitude) que compõem a sequência de segmentos de reta que, conectados, representam seu trajeto. Uma busca consiste em descobrir quais dessas figuras cortam um determinado ponto (idealmente com alguma tolerância).

Calcular a distância entre o ponto e cada um dos segmentos de reta já estaria fora de questão se estivessemos falando de geometria euclidiana simples (e não estamos). Já que a idéia era ter alguma tolerância mesmo, eu poderia verificar se o ponto está na caixa que contém o segmento de reta (reduzindo a questão a uma quadra de comparações de desigualdade). Infelizmente, 4 comparações x cerca de 620 mil pontos ainda é muita coisa.

A salvação da lavoura foi o geohash – essencialmente uma representação de uma área geográfica com precisão mais-ou-menos arbitrária (consulte o link para detahes, é um conceito genial). A biblioteca de geohash que eu usei permite “somar” dois geohashes e retornar o geohash da menor caixa que contém os dois pontos originais.

Limitando essa caixa em 6 caracteres, ficamos com um erro menor que 1 Km – e esse erro é exatamente a margem de manobra que eu precisava. Observe que muitos dos segmentos caem na mesma caixa, logo, uma linha típica (que era composta de várias centenas de pontos/segmentos) acaba “participando” apenas de umas poucas dezenas de geohashes de caixa desse tipo.

Quando o sistema precisa procurar quais linhas passam perto de um ponto geográfico, ele calcula o geohash desse ponto, corta nos 6 caracteres e simplesmente busca as linhas que possuem segmentos cuja string de geohash bata com esse valor calculado. Trocamos aquelas 4 x 620 mil comparações de desigualdade (que o App Engine não iria conseguir combinar mesmo, por estarem em dois campos diferentes – latitude e longitude) por uma única comparação de igualdade (ok, numa string, mas bem curtinha) feita sobre universo de pouco menos de de 2000 hashes distintos – uma bela otimização.

Esse tipo de busca é muito rápida em um banco de dados relacional corretamente modelado e indexado – e me surpreendi quando a performance inicial foi tão ruim que as buscas geralmente davam timeout! O fato é que a maneira com que o App Engine expõe o BigTable para aplicações Python/Java pode levar o desenvolvedor a tratá-lo como um banco de dados relacional, e foi o que eu fiz: tinha uma entidade Linha, uma entidade Ponto, e em cada ponto eu tinha o geohash do segmento que ele formava com o anterior.

Para a coisa dar certo, foi preciso desnormalizar um pouco: fiz a entidade Hash armazenar, para cada geohash de 6 caracteres (que tenha surgido em algum segmento) as chaves primárias de todas as linhas que passam por ele. Com isso, a busca ficou suficientemente rápida.

Uma segunda desnormalização foi armazenar em cada entidade Linha todos os hashes pelos quais ela passa, e retornar essa informação junto com o nome/URL da linha. Isso permite que o próprio JavaScript determine as linhas que ligam dois pontos: ele já tem a lista das linhas que passam em cada um deles, basta ver quais delas têm pelo menos um geohash em comum.

O uso do memcache melhora ainda mais a performance dessas chamadas. A cada busca, guarda-se em cache a lista de linhas para um geohash (beneficiando outros pontos que estejam na mesma “caixa”, cujo resultado é o mesmo) e os meta-dados de cada linha (em separado da lista, já que outros pontos podem retornar a mesma linha e aproveitar esse outro cache).

A outra chamada que o cliente tem que fazer é a lista de pontos da linha em si, para desenhar o trajeto. Ao invés de retornar isso na lista de linhas, achei melhor deixar que ele faça uma nova chamada para cada linha, quando e se precisar dela. Nnovamente o memcache tem a mesma granularidade, fazendo com que o desenho de uma linha seja cacheado independente do ponto utilizado na busca.

Com isso tudo arrumado, a aplicação ganhou corpo suficiente para ir para o ar, e a repercussão me fez ver que não era só eu que sentia falta dessa funcionalidade. Ainda falta uma boa versão mobile, e outros sites bacanas poderiam ser feitos com esses dados. Será que se eu disponibilizar uma API (via YQL, por exemplo) alguém se habilita?

Comments



Olimpio

Uma coisa não ficou muito clara pra mim. Você armazena o trajeto das linhas de que maneira? Numa tabela que tem uma lista de pontos agrupados por uma chave estrangeira?
Ou você utiliza um banco de dados com uma extensão espacial, como o PostgreSQL + Postgis?


chester

Olimpio,

Em vocabulário relacional, seria isso mesmo: uma tabela de linhas e uma de pontos, e uma relação 1-N em que um ponto pertence a uma linha via PK, mais um campo extra para ordenar sequencialmente os pontos.

O que eu fiz é a versão BigTable disso. E para otimizar as buscas (já que eu não tinha um sistema com o o PostGIS) entrou o conceito de geohash que eu descrevi acima.


Olimpio

É que no POSTGIS há funções que fazem os cálculos que vc mencionou, bastando passar como parâmetro o ponto em que o usuário clicou e o valor em metros de influência do ponto. Então a função faz a busca geográfica nos itinerários pré-armazenados e retorna as linhas que atendem às condições.
Sem a extensão fica complicado mesmo, vide o esforço que vc teve pra chegar no resultado.
De qualquer forma, parabéns! Quem não tem cão caça com gato! ;)



Learn how to write in Markdown with this Quick Reference.