Dijkstra aplicado

Março 9, 2009

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

Anúncios

Pré-compilador para o gcc

Março 2, 2009

Recentemente escrevi um programa que faz a inclusão de bibliotecas “locais” no código. Isso é uma das coisas que o gcc faz no primeiro passo na hora de compilar, porém também inclui as bibliotecas padrões, substitui as macros, etc. O que motivou a fazê-lo foi a necessidade de enviar apenas um arquivo de código-fonte de tamanho limitado para ser compilado remotamente em um servidor.

Como o servidor não possuia minhas bibliotecas “locais”, eu deveria inclui-las no único arquivo enviado. Uma possibilidade seria pré-compilar o código fonte com o próprio gcc usando o parâmetro -E. Entretanto, bibliotecas padrões tipo o “stdio.h” são muito extensas e o tamanho do código a ser enviado era limitado.

Esse pré-compilador é então adaptado para incluir apenas bibliotecas que se encontram em diretórios passados por parâmetro. Ele também processa macros da forma #ifndef – #define – #endif usadas em bibliotecas para que o código não seja incluído mais de uma vez.

Uma pequena documentação e o código podem ser acessados aqui.