No semestre passado eu tive a oportunidade de fazer um projeto muito bacana no mestrado. Eu cursei uma matéria chamada Geometria computacional, que como o próprio nome diz, estuda algoritmos clássicos para resolver problemas geométricos. Como projeto final, tivemos que criar um “simulador visual” de um dos problemas geométricos que estudamos. A idéia era implementar o algoritmo força-bruta que resolve o problema e um algoritmo assintoticamente mais rápido, tudo isso de uma forma que o usuário pudesse ver o que o algoritmo está fazendo a cada instante.
Eu e mais um colega de classe resolvemos implementar os algoritmos que resolvem o problema de localizar intersecção de segmentos no plano, ou seja, dado um conjunto de n retas no plano localizar quais delas se intersectam. O Alexis, um ex-aluno do ime-usp, desenvolveu no ano que ele fez essa matéria toda uma interface gráfica bem modular para esse tipo de projeto feita em Python. Como Python é uma linguagem muito massa e seria bem mais simples usar essa interface que ele desenvolveu do que criar uma nossa do zero, resolvemos usar ela para o nosso projeto.
Implementamos um algoritmo conhecido como Shamos & Hoey(SH) que encontra a primeira interseção em um conjunto de n segmentos de reta. Esse algoritmo possui complexidade O(nlgn), e para atingir essa complexidade ele requer uma estrutura de dados que busca um elemento em um conjunto de n elementos em tempo O(lgn). Sendo assim, resolvemos implementar o algoritmo com três sabores: Com Árvore de Busca Binária Balanceada, Árvore de Busca Binária Sem Balanceamento e Skip List. A idéia resumida do algoritmo é analisar todas as retas, mas ao invés de testar a intersecção de cada uma com todas as outras, ele testa apenas a reta logo acima e a logo abaixo da que está sendo analisada, pois obviamente, se estas duas não intersectam a reta, nenhuma outra intersecta, dada uma linha de varredura sobre o eixo x. Além disso, implementamos a versão Força-Bruta que consome tempo O(nˆ2), já que pra cada reta analisada, ele verifica a intersecção com todas as outras.
Segue abaixo alguns screenshots com o resultado final:
No exemplo mostrado, como a árvore de busca não crescia muito, o tempo entre a execução com árvore balanceada e não balanceada foram equivalentes, mas em casos onde a árvore cresce(existem exemplos deste no código) é bem bacana ver a diferença que dá usar uma árvore balanceada. A diferença entre o algoritmo de SH e o Força-Bruta então é gritante. Um programa como esse é legal para abrir os olhos daqueles que não dão valor para Analise de Algoritmos. Se você não acredita o quanto um algoritmo O(nlgn) é melhor que um O(nˆ2), agora você pode ver e comprovar. =)
Coloquei o código no GitHub para caso alguém se interesse por olhar e/ou rodar o programa. Está em http://github.com/luizhespanha/geometry-algorithms-simulation
Muito interessante… Você tava meio sumido. Me diga uma coisa, Luiz, quantos anos você tem? Você trabalha e faz mestrado né? Como que consegue conciliar as duas coisas?
Meu caro gostaria de saber que funções utilizou é que me encontro a ter uma cadeira muito parecida que se denomina algoritmos de computação gráfica e gostaria de implementa-los em python
Qualquer ajuda que me possa dar o meu e-mail é zelitto@hotmail.com
Grato por tudo
É um simulador excelente! O que o Cassio havia feito para o professor Coelho tambem era muito bom e foi usado durante muito tempo nas aulas!