RE: embrulho para presente

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

Paulo Eduardo Azevedo Silveira writes:
 > 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.


É isso ai.

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

Perfeito.

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


Acho que basta você alterar a função Right(p[i_0],p[j_0],p[j])
 para retornar verdadeiro quando os pontos são colineares e p[j] está mais
 distante de p[i_0] do que p[j_0]. Com essa alteração acho que tudo fica ok.

té +,
coelho