Aprofundando os conhecimentos de grafo com o Google Earth
Aprofundando os Conhecimentos de Grafo com o Google Earth
¹Naidion Concencio Brovedan, ²Kristian Madeira
¹ Acadêmico do Curso de Ciência da Computação – Unidade Acadêmica de Ciências,
Engenharias e Tecnologias - Universidade do Extremo Sul Catarinense (UNESC) –
Criciúma, SC – Brasil.
² Professor(a) do curso de Ciência da Computação - Unidade Acadêmica de Ciências,
Engenharias e Tecnologias - Universidade do Extremo Sul Catarinense (UNESC) –
Criciúma, SC – Brasil
[email protected], [email protected]
Resumo: O seguinte artigo foi desenvolvido como projeto para a disciplina de teoria dos grafos do primeiro semestre de 2009, e teve a intenção de reconhecer grafos em softwares com aplicação populares. Para tal feito, os acadêmicos se envolveram na elaboração do projeto com pesquisa e prática efetuada dentro e fora de sala.
Palavras-Chave: Grafos, Google Earth, Dijkstra, Software.
1. Introdução
O presente artigo tem como objetivo reconhecer e explicitar algoritmos de grafos utilizados no software Google Earth e seu uso em aplicações populares. Para isso será dividido em três partes explícitas, a primeira contendo uma descrição para conhecimento de Teoria dos grafos, outra sobre o software usado e outra ainda reconhecendo todas as características de grafos usados no software.
2. Teoria dos Grafos
O primeiro relato de teoria dos grafos que se tem conhecimento foi um artigo de um matemático nascido na Suíça em 1707. Leonhard Paul Euler publicou o problema das Sete Pontes de Könisberg em 1736, o qual relatava um problema que era muito discutido na época. Könisberg possuía sete pontes e duas grandes ilhas e todos verificavam a possibilidade de chegar a todos os lugares passando apenas uma vez por cada ponte. Tomando esse problema, Euler transformou os caminhos em retas e as intersecções em pontos, o que possivelmente tenha sido o primeiro grafo da história. Partindo desse princípio, Euler afirmou que seria impossível fazer tal percurso, há menos que a cada ponto haja um número par de caminhos. De lá para cá, a teoria dos grafos foi amadurecendo e passou a ser usada no dia a dia da população. A sua maior aplicação está à resolução de problemas de trânsito, transporte e localização, e por isso é grande o número de algoritmos computacionais a fim de determinar caminhos e localizações. Pela grande quantidade e até obscuridade sobre eles, este artigo trará somente uma abordagem sobre o algoritmo de Dijkstra.
2.1 Algoritmos de Dijkstra
Edsger Dijkstra, nascido em Roterdã 1930, famoso cientista da computação por contribuir na área de desenvolvimento de algoritmos e programas, desenvolveu um algoritmo para solucionar o problema do caminho mais curto. Tomando um vértice como raiz da busca, este algoritmo tem a função de calcular o custo mínimo deste vértice entre os demais vértices do grafo. O algoritmo pode ser usado sobre grafos orientados ou não, com arestas de peso positivo, com valor igual ou maior que zero. Um exemplo que se enquadra perfeitamente nesse contexto é uma rede de transportes, possui arestas (caminhos) com peso sempre maior que zero, onde se deseja localizar a menor rota entre Criciúma e Florianópolis. O algoritmo atribui valor zero para a origem e começa, então, a elaborar estimativas pessimistas da origem para as demais cidades (vértices), até chegar ao ponto desejado. Depois de n iterações, onde n é o número máximo de caminhos possíveis, o algoritmo mostrará o caminho onde há um menor peso, ou seja, um menor caminho.
3. Google Earth
O Earth Viewer, atualmente conhecido como Google Earth®, foi desenvolvido inicialmente pela Keyhole Inc., uma empresa fundada em 2001 e marcada pelo pioneirismo no desenvolvimento de softwares de visualização espacial. Vendo o sucesso do programa, em 2004 a Google adquiriu a empresa e todos os direitos sobre seus produtos, incluindo o Earth Viewer, que foi reformulado e relançado em 2005 com enorme sucesso. A partir daí, o software foi sofrendo atualizações com imagens de alta definição obtidas através de satélites, aeronaves e também pelo GIS (sistema de informação geográfica), chegando à versão 5.0, sendo então disponibilizado para ambientes Windows®, Linux e MacOS®, nas versões gratuita e paga. Com o software é possível descobrir endereços, marcar rotas, medir distância entre pontos, medir caminhos, marcar locais, escolher rotas, além de API´s para desenvolveres de sistemas georeferenciado. Em 2007 foi lançada a versão web do aplicativo, o googlemaps se tornou referencia em sistema de visualização geográfica, atingindo assim toda a polução, permitindo-lhes localizar residências e locais rapidamente, além de dar a incrível sensação de ver a o planeta do espaço.
4. Grafos e o Software
Como descrito acima, o software utilizado nessa atividade, foi escolhido por usar um conceito de grafo muito perceptível, a escolha do menor caminho. Tendo como principal ferramenta o algoritmo de Dijkstra, o Google Earth sempre mostra o caminho mais curto entre os dois locais escolhido pelo operador. Na opção caminho, os nós, junções de ruas, são destacados com um ponto amarelo e as arestas, sendo então as ruas, destacadas com uma coloração roxa. A junção de tudo isso, resulta num caminho com descrição de todas as ruas e ligações que devem ser feitas para alcançar o ponto de chegada. Já na opção medir caminho, os nós são pontos vermelhos que indicam a mudança de rumo do caminho, e as arestas, são linhas amarelas que destacam o caminho percorrido. A junção resulta num caminho com a distância percorrida, permitindo selecionar a unidade de medida.
5. Referências
NETTO, Paulo Oswaldo Boaventura. Grafos: Teoria, Modelos, Algoritmos. São Paulo: Editora Edgard Blücher, 2003. 307 p.
Tudo Sobre o Google. Disponível em: http://www.google.com.br/about.html Acesso em: 15 de jun de 2009.
