Computação Gráfica - PPGCC

Prof. Márcio Sarroglia Pinho

Trabalho II – Algoritmos de Geometria Computacional

DESCRIÇÃO

O objetivo deste trabalho é comparar o desempenho de um algoritmo de Geometria Computacional com a solução “ingênua”.

Implementar uma solução ingênua para um de Geometria Computacional. Executar o algoritmo sobre um conjunto de dados, registrando o tempo de execução e o gasto de memória, em vários casos.

Escolher um dos algoritmos de Geometria Computacional e executá-lo sobre o mesmo conjunto de dados, registrando o tempo de execução e o gasto de memória.

Descrever o algoritmo em detalhes, montando um texto e uma apresentação, de no máximo 25 minutos.

Para evitar que dois alunos apresentem o mesmo algoritmo, ao selecionar uma opção, o aluno deve encaminhar um e-mail para pinho@pucrs.br para validar a escolha.

Temas já selecionados:

        

Aluno	Problema	Agoritmo
Adriel Silva de Araújo	Line Segment Intersection	Sweep Line algorithm
Lucas Bertoglio Ciocari	Closest pair problem	Divisão e conquista
Maurício Steinert	Convex hull	Algoritmo de Seidel – Kirkpatrick
Natanael Kuniechick	Convex hull	Algoritmo de Andrew
Giuseppe Generoso	Polygon triangulation	Ear clipping algorithm

 

 

Caso haja interesse de escolher um problema já selecionado, o algoritmo deve ser diferente.

ATENÇÃO: Aqueles que já selecionaram o problema, mas não selecionaram o algoritmo, devem fazê-lo o quanto antes e avisar o professor por e-mail.

 

ALGORITMOS

Closest pair problem - 

Encontrar o par mais próximo em um conjunto de pontos

Polygon triangulation -

·      Triangularizar um polígono côncavo

·      Ear clipping algorithm

Convex Hull – Algum algoritmo diferente daqueles que vimos em aula

·      Kirkpatrick–Seidel algorithm

·      Monotone chain, (Andrew's algorithm)

·      Graham scan

Line segment intersection

·      Encontrar todas as interseções entre linhas

·      Bentley–Ottmann algorithm

FONTES DE CONSULTA

https://www.inf.pucrs.br/~pinho/CG-PPGCC/Trabalhos/T4-2020-1/CompGeom_in_C.zip

https://www.topcoder.com/thrive/articles/Line%20Sweep%20Algorithms

https://github.com/CGAL/cgal

http://rosettacode.org/wiki/Closest-pair_problem/C

https://en.wikipedia.org/wiki/Closest_pair_problem

https://en.wikipedia.org/wiki/Polygon_triangulation

https://www.cs.cmu.edu/~quake/triangle.html

https://www.inf.pucrs.br/~pinho/CG-PPGCC/Trabalhos/T4-2020-1/Triangularization.zip

http://rosettacode.org/wiki/Closest-pair_problem

https://sites.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf