Instituto de Matemática Pura e Aplicada

Geometria Computacional - 2001

2a Lista de Exercícios

Para 24/04/2001

1. 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)?

2. Este problema aborda uma forma de determinar a orientação de um polígono simples
   P = p₁p₂...p_n diferente da vista em aula.

1. Seja p_i 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 p_i–1p_ip_i+1.
2. É realmente necessário que p_i seja o vértice de abscissa mínima?
3. 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?

3. Seja P = p₁p₂ … p_n 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.

4. 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 P₁, P₂ e P₃ e um segmento de extremos A e B. Sejam (a₁, a₂, a₃) e (b₁, b₂, b₃) as coordenadas baricêntricas de A e B em relação a P₁, P₂ e P₃.

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.

3. 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, P₁P₂), utilizando coordenadas baricêntricas.