MAC-IME-USP CARLOS EDUARDO FERREIRA
SALA 297A TEL.: 818 6140
E-MAIL cef@ime.usp.br
Este exercício-programa deve ser entregue pelos alunos de graduação em duplas. O exercício não é obrigatório para os alunos de pós-graduação. Os alunos de pós poderão trocar a apresentação pelos EPs, mas deverão fazê-los individualmente.
Implemente o algoritmo visto em sala de aula para determinar o fecho convexo em três dimensões de um conjunto de pontos. Para visualizar a saída vocês utilizarão um programa feito em C pelo Luciano Silva. A documentação a respeito está em:
http://www.ime.usp.br/
coelho/mac747/luciano.ps
O visualizador foi desenvolvido para Macintosh, mas está sendo portado para outras plataformas e estará disponível em breve.
A entrada deste exercício-programa será dada através de um arquivo texto, em que será dada uma instância: a primeira linha contém o número n de pontos da instância e nas n linhas seguintes são dadas as coordenadas de cada um dos pontos (três números reais). A saída esperada será também um arquivo texto no formato esperado pelo visualizador. Lembre que o visualizador espera um poliedro em que todas as faces são triângulos. Assim, o formato esperado é o seguinte: na primeira linha temos o número m de faces do poliedro, e nas 3m linhas seguintes temos as coordenadas dos vértices que formam estas m faces. Nas três primeiras linhas os vértices da primeira face, nas três linhas seguintes da segunda, etc.
Observação: a implementação correta da estrutura de dados ``winged edge'' pode demandar muito tempo. Usem a lista da disciplina para fazer um desenvolvimento cooperativo desta estrutura.