danigfavero/geometria-computacional

Projetos da matéria MAC0331 do IME-USP.

Projetos Geometria Computacional

Trabalhos e exercícios da matéria MAC0331, ministrada pela professora Cristina Gomes Fernandes no primeiro semestre de 2020.

Implementação visual de algoritmos no Tkinter

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.

Problemas do VJudge (programação competitiva)

• Art Gallery
• Closest Pair
• Polygon
• Moth Eradication
• Windy Path
• Saint John's Festival