Trabalho Prático 1 - Problema da Galeria de Arte
Nesse trabalho serão abordados os aspectos práticos de geometria computacional. Especificamente, serão explorados aspectos de implementação do problema da galeria de arte (triangulação de polígonos).
O objetivo secundário é fixar o conteúdo. Entende-se que ao implementar os algoritmos o aluno conseguirá compreender melhor os conceitos explorados. Dessa forma, o conteúdo teórico será melhor absorvido e fixado. Em particular, como os métodos serão implementados de forma gráfica, os alunos poderão visualizar seu funcionamento.
Os alunos deverão implementar um algoritmo para resolver o problema da galeria de arte. Para tal, deverão implementar o algoritmo de triangulação de polígonos Ear-Clipping. Em seguida deverão obter uma 3-coloração do grafo do grafo obtido pela triangulação, apresentando a solução para o problema.
As etapas deverão ser implementadas de forma gráfica. Assim, as arestas analisadas pelo algoritmo Ear-Clipping deverão ser plotadas no gráfico, bem como os vértices em processamento. Cada etapa, triangulação e coloração, deverá ser executada individualmente para que o funcionamento dos algoritmos possam ser visualizados de forma didática.
Os algoritmos deverão ser implementados em Python. Os gráficos deverão ser plotadas com a biblioteca HoloViews, usando o backend Bokeh. As implementações deverão ser feitas em Notebooks de Jupyter e armazenadas em um repositório no GitHub. Os repositórios do projeto deverão ser publicados na data de entrega do trabalho prático, permitindo o acesso pelo professor.
Deverá ser entregue um relatório descrevendo a implementação, onde serão detalhadas as escolhas feitas para implementar os algoritmos; isto é, as estruturas de dados usadas, a forma de implementar e os testes realizados. Também deverá ser feita uma explicação do método com as palavras do aluno.
Como dito anteriormente, a implementação deverá ser disponibilizada em um repositório no GitHub com a implementação em um notebook Jupyter.
Deverão ser observados os critérios de boas práticas de programação, incluindo documentação, identificadores de variáveis, etc.