Primeiro Projeto: aquecimento!

Duas possibilidades:

1. Par de pontos mais próximos [Antonio, Guilherme, Lucas, Marcelo, Marcos, Rafael]
   Implementar o algoritmo de divisão e conquista que vimos na aula 1.
   Data de entrega: 3 de abril.
2. Triangulação de polígonos [Arthur, Leo, Leonardo, Luciano, Max, Théo]
   Implementar o algoritmo quadrático de triangulação por remoção de orelhas que será visto na aula 3, do dia 28 de março.
   Data de entrega: 10 de abril.

Segundo Projeto: linha de varredura - nível 1

1. Par de pontos mais próximos []
   Implementar o algoritmo de linha de varredura, com uma ABB simples, que por exemplo aparece brevemente descrito aqui.
2. Detectar interseção de segmentos [Antonio, Arthur, Guilherme, Léo, Leonardo, Lucas, Luciano, Marcelo, Marcos, Max, Rafael, Théo]
   Implementar o algoritmo de Shamos e Hoey, de linha de varredura, com ABB simples.

Terceiro Projeto: linha de varredura - nível 2

1. Triangulação de polígonos [Antonio, Arthur, Max, Rafael, Theo]
   Implementar o algoritmo de Lee e Preparata com uma ABB balanceada a sua escolha.
2. Todas as interseções de uma coleção de segmentos [Guilherme]
   Implementar o algoritmo de Bentley e Ottmann com uma ABB balanceada a sua escolha.
3. Segmentos visíveis a partir de um ponto [Leo, Leonardo, Marcelo]
   Implementar um algoritmo de linha de varredura com uma ABB balanceada a sua escolha.
Dado um conjunto S de n segmentos de reta disjuntos no plano e um ponto p que não pertence a nenhum dos segmentos de S, determinar todos os segmentos de S que são visíveis a partir de p, isto é, todos os segmentos de S que contém algum ponto q tal que o segmento aberto pq não intersecta nenhum dos segmentos de S.
4. Diagrama de Voronoi [Luciano, Marcos]
   Implementar o algoritmo de Fortune para construir o diagrama de Voronoi. Trata-se de um algoritmo de linha de varredura. Use uma ABB balanceada a sua escolha para implementar a linha de varredura.

Quarto Projeto: diversos

1. Triangulação de Delaunay [Antonio, Leonardo, Luciano, Max]
   Implementar o algoritmo probabilístico visto na aula 12 para construir a triangulação de Delaunay.
2. Localização de pontos [Guilherme, Marcelo, Marcos]
   Implementar os dois algoritmos vistos na aula 13 para localização de ponto: o ray crossing e o winding number.
3. Par de pontos mais próximos [Arthur, Rafael, Theo]
   Implementar os dois algoritmos (linha de varredura e probabilístico) vistos na aula 14 para encontrar o par de pontos mais próximos.

Quinto Projeto: fecho convexo

1. Embrulho de presente e algoritmo de Graham [Antonio,Arthur,Leo,Max,Theo]
   Implementar os algoritmos de Jarvis (embrulho de present) e de Graham para o fecho convexo 2D.
2. Quickhull [Leonardo,Marcos]
   Implementar o algoritmo Quickhull para fecho convexo 2D.
3. Mergehull [Guilherme, Rafael]
   Implementar o algoritmo Mergehull para fecho convexo 2D.
4. Embrulho de presente 3D [Luciano]
   Implementar o algoritmo Embrulho de presente para fecho convexo 3D.

Regras

• Todos os algoritmos devem ter uma animação que mostre claramente o seu funcionamento, como as animações disponibilizadas na plataforma e outras mostradas nas aulas.

O que você deve entregar

• Uma implementação na plataforma disponibilizada do algoritmo escolhido o mais eficiente possível.
• Uma animação do algoritmo escolhido, nos moldes das animações disponibilizadas na plataforma e outras mostradas nas aulas.
• Um arquivo README em que descreve exatamente o que foi implementado e em que condições está a sua implementação: se está funcionando completamente, se está quase funcionando (diga em que casos não está funcionando), se está ruim, com vários problemas (especifique, para ajudar no processo de correção).