| Resumo: | O problema de geração aleatória de objectos geométricos tem sido alvo de uma intensa actividade de investigação. A importância dada a este classe de problemas deve-se ao facto de permitir a simplificação da avaliação de algoritmos. É frequente a impossibilidade de obter dados reais, de problemas e aplicações do dia-a-dia, que permitam testar determinados algoritmos. Assim, a geração aleatória de objectos geométricos é sem dúvida uma boa alternativa para simular, o mais possível, situações reais. Nesta dissertação abordamos um desses problemas: o problema de geração aleatória e uniforme de polígonos simples. Devido ao facto de que até agora não se conhecem algoritmos minimamente eficientes para este problema, tornou-se necessário o desenvolvimento de métodos heurísticos que permitem gerar uma variedade considerável de diferentes polígonos. São diversos os trabalhos que contribuíram para este estudo, os quais serão referidos ao longo desta tese. Com o objectivo de testar e avaliar experimentalmente um subconjunto das heurísticas analisadas foi desenvolvida uma aplicação que inclui uma interface gráfica para facilitar a introdução de dados de entrada (pontos) e a visualização dos resultados (polígonos gerados) por parte do utilizador. Esta aplicação é descrita detalhadamente nesta dissertação.
|
|---|