Geometria Computacional
 2009


Trabalho para 22/9

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

  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?

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