Instituto de Matemática Pura e Aplicada
Geometria Computacional - 2001
2a Lista de Exercícios
Para 24/04/2001
- Mostre que a área de um quadrilátero convexo plano abcd
é dada por S = |ac ´
bd|. A fórmula continua válida se o
quadrilátero não é convexo (mas é simples)?
- Este problema aborda uma forma de determinar a
orientação de um polígono simples
P = p1p2...pn
diferente da vista em aula.
- Seja pi o vértice de P de abscissa mínima
(se houver mais que um, escolha dentre eles o que também
tem ordenada mínima). Diga como obter a orientação de P
a partir da orientação do triângulo pi1pipi+1.
- É realmente necessário que pi
seja o vértice de abscissa mínima?
- Em sala foi feita a afirmativa de que a orientação de
um polígono é uma propriedade global do
polígono. O método em (a) contradiz esta afirmativa?
- Seja P = p1p2
pn um polígono convexo
do plano. Diga como determinar se um ponto p do
plano é interior ou exterior a P, em tempo O(log
n), supondo que os vértices estejam armazenados
em um vetor. Explique porque isto não vale se os
vértices estão armazenados em uma lista encadeada.
- O problema de clipping
(ou recorte, ou cerceamento) é extremamente relevante em
Computação Gráfica. Dada uma curva e um polígono,
deseja-se saber que porções desta curva são interiores
ao polígono. Neste problema, consideraremos o caso
particular em que a curva é um segmento de reta e o
polígono é um triângulo. Consideremos um triângulo de
vértices P1, P2 e P3
e um segmento de extremos A e B. Sejam (a1, a2, a3) e (b1, b2, b3) as coordenadas
baricêntricas de A e B em relação a P1,
P2 e P3.
- Que condição deve ser satisfeita para que o
segmento AB esteja completamente contido
no triângulo?
- Encontre condições sob as quais podemos
garantir que o segmento AB é
completamente exterior ao triângulo.
|
|
- Suponha que ambos os testes acima
falhem para o segmento AB. Diga
como encontrar o ponto
em que o segmento corta um dado lado (por exemplo, P1P2), utilizando coordenadas baricêntricas.