Geometria Computacional - 2007

Trabalho para 26/4

O objetivo do trabalho é comparar algoritmos que calculam o fecho convexo de um conjunto de pontos no plano.
  1. 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.

  2. 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. Veja uma figura gerada por um programa em PostScript.

  3. 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.

  4. Refaça os testes do item anterior incorporando eliminação de pontos interiores. Vale a pena eliminar pontos interiores?

O trabalho deve ser apresentado e entregue ao Emilio até o dia 26/4.

Last update: Thu Mar 22 13:11:22 BRST 2007