RE: embrulho para presente

[Jose Coelho de Pina <coelho@ime.usp.br>]

Antes tarde do que nunca...  
      
   
Paulo Eduardo Azevedo Silveira writes:
 [...]
 > ja estou meio perdido nos nomes dos algoritmos do fecho convexo, sao
 > zilhares! mas o embrulho pra presente eu esqueci de vez!

É verdade.

 > 
 > ele tem de ser O(nh), entao para cada aresta devo fazer N comparacoes no
 > maximo. Ja tendo uma aresta do fecho, eu tenho de achar o ponto que tem
 > menor angulo polar com a aresta anterior, eu nao sei fazer isso!
 [...]
 > 
 > a pergunta: como uso o LEFT para descobrir o ponto que tem menor angulo em
 > relacao a uma dada aresta?
 > agora to pensando direito, e isso tambem eh usado no graham para o
 > pre-processamento.
 > 

De fato, o Graham usa a mesma ordenação.

Acho que vale a pena descrever o algoritmo embrulho-para-presente, em mais
baixo nível. A descrição é mais ou menos a seguinte. 

#define X      0 
#define Y      1
#define DIM    2
#define PMAX ???

typedef int tPointi[DIM]; 
typedef tPointi tPolygoni[PMAX]; // poligono de pontos inteiros

tPointi    p[PMAX]; // guarda os pontos dados
tPolygoni  conv;    // guarda o fecho 

[...]

// Encontra o ponto mais `baixo'
   i_0 = 0;
   for (j = 1; j < n; j++)
     {
       if (p[i_0][Y] > p[j][Y]) 
         {
           i_0 = j;
         }
     }   

     // i_0 é ponto fo fecho
     conv[0]= i = i_0; 
     k = 1;    

(1)  while (i != i_0) // enquanto não fechou o polígono 
       {
         // Acha a `próxima' aresta do fecho que tem uma estremidade
         // em i.
         j_0 = 0;
          
(2)      for (j = 1; j < n; j++) 
           {
             if (Right(p[i],p[j_0],p[j]))
               {
                 j_0 = j;
               }  
           }

         // j_0 é o próximo ponto do fecho
         conv[k++] = j_0;
         i = j_0;
       }
    
      // Devolve o fecho convexo 
      for (i = 0; i < k; i++) 
        {
          fprintf(stdout,"i:%d %d\n", conv[i][X], conv[i][Y]);
        }

Comentários:

  O while da linha (1) é executado h vezes, onde h é o número de vértices do
  fechop convexo. O for da lina (2) é executado executado n vezes. Logo, o
  tempo total consumido pelos comando dentro do while é proporcional a 
  nh.

  No código acima estamos supondo que não há 3 pontos colinerares.
  (O que muda se tivermos 3 pontos colineares?).


té +,
coelho