RE: embrulho para presente

[Paulo Eduardo Azevedo Silveira <peas@linux.ime.usp.br>]

Ah
agora eu lembrei

a gente procura o ponto mais a direita de todos, para isso a gente vai
testando se tem alguem a direita, se tiver, pega esse e vai testando com
os que sobraram.

se voce tiver pontos colineares, voce tem duas opcoes, uma eh fazer com
que o teste nao seja RIGHT, e sim RIGHTON, ai voce pega esse novo
candidato e verifica quem dista mais do ponto X, sendo que X eh o
penultimo ponto a ser inserido no fecho.

se voce quer que o fecho nao "coma" vertices, voce pega o que tem menor
distancia com X (e se o que tinha maior antes fazia parte do fecho, agora
sera swapado com o de menor distancia), mas se voce quiser o fecho com
menor numero de arestas possiveis, fique com o de maior distancia, e nesse
caso tambem pode haver um swap de pontos do fecho.

o pior eh que VARIOS pontos podem ser colineares, entao tem de monstar
alguma estrutura de pilha ai para que sempre que encontrado colineares,
tem de fazer teste com os anteriores ateh que nao sejam mais colineares.

isso NAO eh n^2, porque vai descartando os colineares, eles nao serao
comparados N vezes

paulo


Paulo Eduardo A. Silveira   <peas@linux.ime.usp.br>
UIN: 5142673   www.paulo.com.br

On Wed, 6 Jun 2001, Jose Coelho de Pina wrote:

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