Geometria Computacional
Prof. Walter Mascarenhas
Segundo semestre de 2004
Aula 3
Corolários do dual da triangulação ser árvore
• Toda triangulação tem n - 2 triângulos. Prova?
• Todo polígono tem pelo menos duas orelhas.
Prova?
Toda triangulação tem n-2 triângulos
• Prova por indução
• Vale para o triângulo
• Para o caso n:
Aritmética
• Exata: pode ser lenta e consumir muita memória
• Ponto flutuante: rápida mas aproximada e pode
causar erros sutis.
Aritmética de ponto flutuante
Experimentando com o epsilon:
www.ime.usp.br/~walterfm/cursos/mac0331/2004/float.cpp
Exemplo prático
Abacaxis de dois sabores:
•Algoritmos instáveis. Geram soluções ruins, mesmo
para problemas simples. Exemplo: slide anterior.
•Problemas mal condicionados. O coitado do
algoritmo tem pouca chance. Exemplo: raízes duplas.
•Na prática: é só dar o mouse para o usuário...
Há dois tipos de estabilidade:
•A solução calculada está próxima do valor certo.
•A solução calculada é o valor certo para um
problema aproximado. Muito útil para problemas
mal condicionados. Exemplo: Intersecção de retas
quase paralelas.
Áreas de triângulos
Trabalho de W. Kahan (medalha Turing, projetista
das calculadoras da HP.)
www.cs.berkeley.edu/~wkahan/triangle.pdf
Veja também
• What has the Volume of a Tetrahedron to do with
Computer Programming Languages?
• How JAVA’s Floating Point hurst everyone everywhere.
• E muitos outros em www.cs.berkeley.edu/~wkahan
Cultura Geral
What Every Computer Scientist Should
Know About Floating-Point Arithmetic,
por David Goldberg.
http://docs.sun.com/source/806-3568/ncg_goldberg.html
Álgebra Linear
Dois tipos de vetores: posições e deslocamentos.
Agora com eixos:
Mas se o plano fosse curvo...
ele teria um plano tangente (direções)
diferente em cada ponto
O Produto interno: ângulo
Produto interno: projeção
Aplicação: distância de ponto a segmento:
Analisando as projeções
Distâncias:
Primeiro algoritmo de triangulação:
• Idéia básica: Ir removendo orelhas.
• Custo no passo k:
– Achar a orelha dentre n - k (= O(n)) vértices
– Para decidir se o vértice v é orelha:
• Verifique se não é reverso (O(1))
• Verifique se há outros vértices no triângulo (n - k - 3)
– Custo do passo: (n - k) (n - k - 3) = O(n^2)
• Total, n - 3 passos => Custo O(n^3)
Pergunta:
Será que ao remover uma orelha eu não estrago o polígono?