Dijkstra aplicado

Acho que desde o primeiro ano tinha vontade de saber qual era o melhor jeito de ir do IC-3 à FEEC ou vice-versa. É porque a Unicamp possui as ruas aproximadamente concêntricas em relação ao CB (Ciclo Básico) e como o IC-3 e a FEEC estão no “anel” mais externo, talvez compensasse ir até uma rua mais interna, percorrer um arco menor e depois voltar à rua mais externa.

Na época eu queria considerar o modelo aproximado e calcular a partir de qual ângulo compensava ir aos anéis mais internos ao invés de contornar o anel mais externo. Acabei deixando a idéia de lado.

No começo desse primeiro semestre de 2009, estava estudando um pouco de Javascript e acabei descobrindo o canvas, uma nova marcação HTML suportada pelos browsers mais modernos (isso exclui o Internet Explorer em quaisquer versões, obviamente =P) e que pareceu se adequar bem aos meus propósitos, que era a de usar um mapa da Unicamp e a partir dele traçar menores caminhos.

Bom, minha primeira idéia era usar o Google Maps. Fiquei com preguiça de estudar a API deles e vi que o mapa da Unicamp no site da prefeitura da Unicamp [1] é mais detalhado.

Escolhido o mapa, pensei em usar algum tipo de processamento de imagens para determinar os caminhos possíveis, ou seja, identificar as ruas e seus comprimentos. Outra abordagem seria traçar os caminhos manualmente, aproximando curvas por retas e colocando vértices onde duas ou mais ruas se encontram. A primeira idéia tem a vantagem de ser mais prática, pois não tenho que ficar inserindo vértice a vértice, sem contar que a modelagem ia ter uma precisão muito boa, pois curvas seriam aproximadas a nível de pixel. Entretanto, o que me fez optar pela segunda opção foi que estando a pé, utilizamos muitos atalhos, passando por dentro dos institutos ou andando sobre a grama, caminhos estes que o algoritmo nunca encontraria.

Inseri alguns vértices, principalmente ao redor do CB (deixei de lado por enquanto a vizinhança do HC). Acho que foram cerca de 50 vértices e 100 arestas colocados manualmente (=/).

O problema é facilmente modelável para o problema de menores caminhos ponderado, onde o peso nas arestas é a distância euclidiana entre dois pontos na imagem. Deixo o usuário escolher quaisquer dois pontos de origem e destino na imagem. Como esses vértices não são necessariamente vértices do grafo, temos que dar um jeito de inclui-los. Seja ‘p’ o ponto de origem (serve pro ponto de destino). Encontramos a aresta ‘E’ mais próxima de ‘p’ e achamos ‘q’, o ponto mais próximo de ‘p’ na aresta ‘E’. Adicionamos os vértice p e q ao grafo, a aresta (p,q), (q,E1) e (q,E2), onde ‘E1’ e ‘E2’ são os endpoints de ‘E’. O algoritmo de Dijkstra resolve bem o problema e então traça o menor caminho da fonte ao destino definidos.

Adicionalmente coloquei uma legenda na imagem. Quando o usuário passa o mouse sobre um instituto por exemplo, aparece o nome desse instituto, para fins de orientação. Implementei isso do jeito ingênuo: percorre todos os institutos e verifica aquele que está a uma distância especificada do cursor do mouse.

O resultado atual pode ser conferido nessa página

Referências:
[1] Mapa do Campus

Uma resposta a Dijkstra aplicado

  1. Vítor diz:

    “Entretanto, o que me fez optar pela segunda opção foi que estando a pé, utilizamos muitos atalhos, passando por dentro dos institutos ou andando sobre a grama, caminhos estes que o algoritmo nunca encontraria.”heauheuahh, fora o fato de que você não tava querendo descobrir como faze por processamento de imagens, foi isso mesmo

%d bloggers like this: