Animacoes
Greiner-Hormann
Foster et al.
Martinez et al.
Estudo de 3 algoritmos para resolver esse problema
Leia maisRealizar operações Booleanas em polígonos pode não parecer, mas é extremamente importante para alguns algoritmos e softwares. Elaborar um algoritmo para encontrar a região resultante da operação entre dois polígonos não é uma tarefa trivial. Nesse trabalho de conclusão de curso, estudamos e implementamos alguns algoritmos para esse problema e fizemos alguns experimentos computacionais para compará-los. Os algoritmos estudados foram os seguintes:
Os motivos da escolha desses três algoritmos se apresentam a seguir. Escolheu-se o algoritmo de Greiner-Hormann, pois foi um dos primeiros a aceitar como entrada polígonos genéricos sem complicar muito o algoritmo. Além disso, esse foi um dos primeiros algoritmos a suportar outras operações Booleanas fora a interseção. Embora esse algoritmo seja de certa forma elegante (por conta de sua simplicidade), ele trata os casos degenerados de maneira indesejada dependendo da aplicação. Nesse sentido, estudou-se o algoritmo de Foster et al, em que tal problema foi resolvido sem complicar muito o algoritmo. O último algoritmo (Martinez et al) foi estudado porque utiliza uma técnica diferente para resolver o problema (linha de varredura) e, por conta disso, tem um desempenho que pode ser melhor.
| Atividade | Mar | Abr | Mai | Jun | Jul | Ago | Set | Out | Nov | Dez | Jan |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Leitura Greiner-Hormann | X | ||||||||||
| Implementação e animação Greiner-Hormann | X | X | |||||||||
| Escrita da Monografia (Greiner-Hormann e Introdução) | X | ||||||||||
| Leitura Foster et al. | X | ||||||||||
| Implementação e animação Foster et al. | X | X | |||||||||
| Escrita da Monografia (Foster et al.) | X | X | |||||||||
| Leitura Martinez et al. | X | ||||||||||
| Implementação e animação Martinez et al. | X | X | |||||||||
| Preparação para o conteúdo da apresentação | X | ||||||||||
| Escrita da Monografia (Martinez et al.) | X | X | |||||||||
| Escrita da Monografia (ajustes finais) | X |
Greiner-Hormann
Foster et al.
Martinez et al.
Aluno: Rafael V. Carvalho
Supervisora: Cristina G. Fernandes