Trabalhos e exercícios da matéria MAC0331, ministrada pela professora Cristina Gomes Fernandes no primeiro semestre de 2020.
1. Triangulação de polígonos
Implementação do algoritmo quadrático de triangulação por remoção de orelhas. Em geocomp-py-framework/geocomp/triangulation/ear_clipping.py
.
2. Detecção de todas as intersecções numa coleção de segmentos
Implementação do algoritmo de Bentley e Ottmann com uma ABB balanceada. Em geocomp-py-framework/geocomp/lineintersection/bentley_ottmann.py
- feito com @bentopereira.
3. Par de pontos mais próximos
Implementação de um algoritmo probabilístico para encontrar o par de pontos mais próximos. Este algoritmo aparece descrito na Sec 13.7 do livro de Kleinberg e Tardos (Algorithm Design). Em geocomp-py-framework/geocomp/closest/prob.py
- feito com @bentopereira.
4. Quickhull
Implementação do algoritmo Quickhull para fecho convexo 2D. Em geocomp-py-framework/geocomp/convexhull/quickhull.py
.
- Art Gallery
- Closest Pair
- Polygon
- Moth Eradication
- Windy Path
- Saint John's Festival