Métodos heurísticos para a geração de polígonos simples

Abstract

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.

The random generation of geometrical objects has been heavily addressed by the scientific community. The importance given to this class of problems is due to the fact that it simplifies the algorithms' evaluation. It is usual not to obtain real data, problems and day life applications that would allow the evaluation of some algorithms. Consequently, the random generation of geometrical objects is undoubtedly a good approach to simulate, as close as possible, real situations. In this dissertation, we study one of such problems: the random and uniform generation of simple polygons. Efficient algorithms are not known to the date, so it is necessary to develop heuristic methods to generate a considerable variety of different polygons. There are several works that contributed for this subject and they will be referred along this thesis. Having in mind an experimental test and evaluation of a subset of the analyzed algorithms, an application that includes a graphic interface has been developed to make it easier for the user to insert data (points) and visualize the final results (generated polygons). There is a detailed description of that application in this thesis.