Trabalho para 22/9
O objetivo do trabalho é comparar algoritmos que calculam o fecho
convexo de um conjunto de pontos no plano.
-
Implemente o algoritmo de Jarvis e o algoritmo por varredura.
Escreva o programa mais simples possível.
Não se preocupe com interfaces gráficas.
-
Teste os seus programas no seguinte conjunto de pontos:
A B C D E F G H I J K L M N O P Q
x 3 11 6 4 5 8 1 7 9 14 10 17 15 13 3 12 16
y 9 1 8 3 15 11 6 4 7 5 13 14 2 16 12 10 8
A solução é B M L N E O G D.
Note que Q não faz parte da solução.
A
figura
mostra a solução e foi gerada por um
programa
em
PostScript.
(É muito útil aprender um pouco de PostScript,
pois é um ferramenta simples que permite gerar figuras precisas.)
-
Compare o desempenho dos dois algoritmos em conjuntos de pontos
gerados aleatoriamente
dentro de um retângulo,
dentro de um triângulo,
dentro de um círculo,
e sobre o círculo.
Use conjuntos de 100, 1000, 10000 e 100000 pontos.
(E mais se for possível.)
Compare os tempos de cada algoritmo e
também o esforço necessário para sua implementação.
-
Refaça os testes do item anterior incorporando eliminação de pontos interiores.
Vale a pena eliminar pontos interiores?
-
Avalie o papel do passo de ordenação no desempenho global dos seus programas.
Qual a diferença de usar
um algoritmo quadrático ou um algoritmo O(n log n)?
O trabalho deve ser apresentado e entregue ao Marcelo até o dia 22/9.
PS:
Leia
o artigo
"Classroom examples of robustness problems in geometric computations"
para discussão no dia 22.
Last update:
Mon Sep 14 13:43:57 BRT 2009