10. Um pouco mais sobre Geometria e Programação Geométrica

Na aula anterior apresentamos os elementos básicos da geometria afim e euclidiana: pontos, vetores e operações como combinações afins e o produto escalar.

No entanto, ainda não temos nenhum mecanismo para definir esses objetos! Hoje vamos tratar de questões mais fundamentais de como representar esses objetos usando sistemas de coordenadas e coordenadas homogêneas.

10.1. Bases, vetores e coordenadas

A primeira questão que precisamos responder é: como representar pontos e vetores no espaço afim?

Para responder essa pergunta, você deve se lembrar da álgebra linear que se tivermos 2 vetores linearmente independentes, \(\vec{u_0}\) e \(\vec{u_1}\) no espaço 2D, então podemos representar qualquer outro vetor em 2D como uma combinação linear desses dois vetores (veja a Figura Fig. 10.1 a):

\(\vec{v} = \alpha_0 \vec{u}_0 + \alpha_1 \vec{u}_1\),

para alguma escolha de escalares \(\alpha_0\) e \(\alpha_1\). Assim, dados quaisquer desses vetores, podemos usá-los para representar qualquer vetor em termos de uma tupla de escalares \((\alpha_0, \alpha_1)\). Em geral, \(d\) vetores linearmente independentes na dimensão \(d\) são chamados de base. A base mais conveniente para trabalhar em 2D consiste em dois vetores, cada um de comprimento unitário, ortogonais entre si. Essa coleção de vetores é dita ortonormal. A base padrão que consiste nos vetores das unidades \(x\) e \(y\) é ortonormal (veja a Figura Fig. 10.1 b).

Fig. 10.1 Base e combinação linear em álgebra linear (a) e base padrão ortonormal (b).

Observe que estamos usando o termo “vetor” com dois sentidos diferentes:

• como entidade geométrica e
• como uma sequência de números, dada na forma de uma linha ou coluna.

O primeiro é o objeto de interesse (ou seja, o tipo de dados abstrato, na terminologia da ciência da computação), e o último é uma forma de representação. Como é comum na programação orientada a objetos, devemos “pensar” em termos do objeto abstrato, ainda que sejamos forçados, na implementação, a trabalhar com a representação.

10.2. Sistemas de Coordenadas

Agora vamos voltar a pensar de forma abstrata dentro da geometria afim. Parece natural generalizar a noção de uma base em álgebra linear para definir uma base no espaço afim. Observe que os vetores livres por si só não são suficientes para definir um ponto, já que não há como definir um ponto usando apenas operações com vetores livres. Assim, para definir uma posição, vamos considerar um ponto \(\mathcal{O}\), para servir de origem do nosso sistema de coordenadas.

A partir de \(\mathcal{O}\), qualquer ponto \(P\) pode agora ser definido por um vetor \(\vec{v} = P - \mathcal{O}\). Além disso, esse vetor pode ser descrito por uma única combinação linear dos vetores de base. Assim, dado um ponto origem \(\mathcal{O}\) e um conjunto de vetores de base \(\vec{u}_i\), qualquer ponto \(P\) pode ser expresso univocamente pela soma de \(\mathcal{O}\) com uma combinação linear dos vetores de base:

\(P = \alpha_0 \vec{u}_0 + \alpha_1 \vec{u}_1 + \alpha_2 \vec{u}_2 + \mathcal{O}\)

para alguma combinação de escalares \(\alpha_0, \alpha_1, \alpha_2\). Adotaremos essa forma para representar um sistema de coordenadas para espaços afins.

Sistema de Coordenadas

Um sistema de coordenadas para um espaço afim \(d\)-dimensional consiste de um ponto \(\mathcal{O}\) (chamado de origem do sistema) e um conjunto de \(d\) vetores base linearmente independentes.

10.2.1. Exemplo

A Figura Fig. 10.2 mostra um ponto \(P\) e um vetor \(\vec{w}\).

Fig. 10.2 Sistema de coordenadas. Fonte: Figura 17 das notas de aula do Prof. Mount.

A figura também mostra dois sistemas de coordenadas, \(F\) e \(G\). Usando esses sistemas, podemos expressar \(P\) e \(\vec{w}\) das seguintes formas:

• no sistema \(F\):

  • \(P = 3 \cdot F.\vec{e}_0 + 2 \cdot F.\vec{e}_1 + F.\mathcal{O}\)
  • \(\vec{w} = 2 \cdot F.\vec{e}_0 + 1 \cdot F.\vec{e}_1\)

• no sistema \(G\):

  • \(P = 1 \cdot G.\vec{e}_0 + 2 \cdot G.\vec{e}_1 + G.\mathcal{O}\)
  • \(\vec{w} = -1 \cdot G.\vec{e}_0 + 0 \cdot G.\vec{e}_1\)

10.3. Coordenadas homogêneas

Para representar tanto pontos quanto vetores como uma lista de valores escalares, vamos adotar o seguinte axioma:

Axioma: Para cada ponto \(P\) no espaço afim, \(0 \cdot P = \vec{0}\) e \(1 \cdot P = P\).

Embora esse axioma viole as propriedades da geometria afim, ele nos permite uma notação mais consistente da seguinte maneira:

\(P = 3 \cdot F.\vec{e}_0 + 2 \cdot F.\vec{e}_1 + 1 \cdot F.\mathcal{O}\)

\(\vec{w} = 2 \cdot F.\vec{e}_0 + 1 \cdot F.\vec{e}_1 + 0 \cdot F.\mathcal{O}\)

Com isso podemos usar arrays de mesma dimensão para representar tanto pontos quanto vetores. Para o sistema \(F\) temos:

\(P{[F]} = \begin{pmatrix} 3 \\ 2 \\ 1\end{pmatrix}\) e \(\vec{w}_{[F]} =\begin{pmatrix} 2 \\ 1 \\ 0\end{pmatrix}\)

Chamaremos essa nova notação de coordenadas homogêneas em relação ao sistema \(F\). Em algumas convenções de álgebra linear, os vetores são escritos como vetores linha e outras como vetores coluna. Vamos adotar a mesma convenção do OpenGL, ou seja, de usar vetores coluna, mas podemos ser descuidados de vez em quando.

Como dissemos antes, o termo “vetor” tem dois significados: um como vetor livre em um espaço afim, e agora como vetor coordenadas. Normalmente, ficará claro do contexto qual o significado pretendido. Em geral, para representar pontos e vetores no espaço \(d\)-dimensional, usaremos vetores de coordenadas de comprimento \(d + 1\). Pontos têm a última coordenada 1 e os vetores têm a última coordenada 0. Alguns autores colocam a coordenada homogênea primeiro, em vez de na última posição. Na verdade, existem boas razões para fazer isso, mas manteremos a convenção de colocá-la por último.

10.3.1. Propriedades das coordenadas homogêneas

A decisão de usar 1 para pontos e 0 para vetores não foi arbitrária. Essa escolha resulta em várias propriedades interessantes com relação às operações geométricas.

Por exemplo, considere dois pontos \(P\) e \(Q\) com coordenadas relativas a um sistema de coordenadas \(F\) dadas por: \(P{[F]} = (3, 2, 1)^T\) e \(Q{[F]} = (5, 1, 1)^T\). Considere também o vetor \(\vec{v} = P - Q\). Note que o resultado da subtração entre as coordenadas dos pontos é \(\vec{v} = (-2, 1, 0)^T\), ou seja, com coordenada homogênea 0, que indica que o resultado é um vetor!

De forma geral, a última coordenada indica se o resultado da operação é um ponto ou vetor e, caso o resultado seja diferente de 0 ou 1, significa que a operação realizada é inválida. Isso sugere uma forma de fazer a verificação de tipo para um sistema de geometria livre de coordenadas. Pontos e vetores são armazenados usando um tipo base comum, que consiste simplesmente de um vetor com 4 escalares (floats). Esse sistema permite que o programador execute qualquer combinação de operações padrão com essas coordenadas e, antes da atribuição final, o sistema simplesmente verifica se a última coordenada é 0 ou 1, e se esse valor é compatível com o tipo de variável na qual se está armazenando o resultado.

Isso permite grande flexibilidade na criação de expressões, como:

\(\mbox{centroide} = (P + Q + R) / 3\),

que, de outra forma, seriam consideradas inválidas. Uma desvantagem de tal método de verificação é o aumento da carga computacional em tempo de execução. Uma solução intermediária seria permitir que a verificação seja realizada apenas durante a depuração do programa e possa ser desligada na versão de produção.

10.4. Múltiplos sistemas de coordenadas

Qualquer sistema de programação geométrica deve lidar com dois objetivos conflitantes.

• Primeiro, queremos que pontos e vetores sejam representados em relação a algum sistema de coordenadas universal, para que possamos fazer operações com pontos e vetores usando as listas de coordenadas.
• Mas muitas vezes é desejável definir pontos relativos a algum sistema de coordenadas local, mais conveniente. Por exemplo, latitude e longitude podem ser uma boa maneira de representar a localização de uma cidade, mas não é uma maneira muito conveniente de representar a localização de um caractere nesta página.

Qual o que seria um sistema de coordenadas mais universal?

Vamos apenas adotar, por convenção, um sistema que vamos chamar de sistema padrão a partir do qual todos os outros objetos serão definidos. Será um sistema de referencia ortonormal, o que significa que seus vetores de base são ortogonais entre si e cada um tem comprimento unitário. Denotamos a origem por \(\mathcal{O}\) e os vetores de base por \(e_i\). As coordenadas dos elementos do sistema padrão (no espaço 3D) são definidas como:

\(\vec{e}_0 = \begin{pmatrix}1 \\ 0 \\ 0 \\ 0\end{pmatrix}\), \(\vec{e}_1 = \begin{pmatrix}0 \\ 1 \\ 0 \\ 0\end{pmatrix}\), \(\vec{e}_2 = \begin{pmatrix}0 \\ 0 \\ 1 \\ 0\end{pmatrix}\) e \(\mathcal{O} = \begin{pmatrix}0 \\ 0 \\ 0 \\ 1\end{pmatrix}\).

10.5. Exemplo de mudança de sistemas de coordenadas

Uma das operações geométricas mais importantes em computação gráfica é a de converter pontos e vetores de um sistema de coordenadas para outro. Lembre-se da figura anterior que em relação ao sistema \(F\) temos \(P[F] = (3,2,1)^T\), e \(\vec{w}[F] = (2,1,0)^T\). Derivamos as coordenadas relativas ao sistema \(G\) por inspeção, mas como poderíamos fazer isso computacionalmente?

Nosso objetivo é encontrar escalares \(\beta_0\), \(\beta_1\), \(\beta_2\), tais que

\(P = \beta_0 G.e_0 + \beta_1 G.e_1 + \beta_2 G.\mathcal{O}\).

Dado que \(F\) é um sistema, podemos descrever os elementos de \(G\) em termos de \(F\). Se fizermos isso, teremos \(G.e_0[F] = (-2, -1, 0)^T\), \(G.e_1[F] = (0, 1, 0)^T\) e \(G.\mathcal{O}[F] = (5, 1, 1)^T\). Usando esta representação, segue que \(\beta_0\), \(\beta_1\), e \(\beta_2\) devem satisfazer:

\(\begin{pmatrix}3 \\ 2 \\ 1\end{pmatrix} = \beta_0 \begin{pmatrix}-2 \\ -1 \\ 0\end{pmatrix} + \beta_1 \begin{pmatrix}0 \\ 1 \\ 0\end{pmatrix} + \beta_2 \begin{pmatrix}5 \\ 1 \\ 1\end{pmatrix}\).

Se decompormos essa equação vetorial em seus três componentes, obtemos três equações e três incógnitas. Se você resolver esse sistema de equações (pelos métodos que aprendeu em álgebra linear), descobrirá que \((\beta_0, \beta_1, \beta_2)=(1, 2, 1)\). Daí temos que:

\(P[F] = \begin{pmatrix}3 \\ 2 \\ 1\end{pmatrix} = 1 \begin{pmatrix}-2 \\ -1 \\ 0\end{pmatrix} + 2 \begin{pmatrix}0 \\ 1 \\ 0\end{pmatrix} + 1 \begin{pmatrix}5 \\ 1 \\ 1\end{pmatrix} = 1 \cdot G.e_0[F] + 2 \cdot G.e_1[F] + 1 \cdot G.\mathcal{O}[F]\),

e portanto as coordenadas de \(P\) relativas a \(G\) são

\(P[G] = (1, 2, 1)^T\).

Como exercício, derive a transformação para \(\vec{w}[G]\), sabendo que \(\vec{w}[G]=(-1,0,0)^T\).

10.6. Mudança de coordenadas: caso geral

Gostaríamos de generalizar o processo para um par arbitrário de sistemas de coordenadas. Vamos supor que \(F\) é o sistema padrão, e que podemos definir \(G\) em relação a este sistema padrão fornecendo as coordenadas para os vetores de base \(G.e_0\), \(G.e_1\) e o ponto de origem \(G.\mathcal{O}\) em relação ao referencial \(F\):

\(G.e_0[F] = (g_{00}, g_{01}, 0)^T\),

\(G.e_1[F] = (g_{10}, g_{11}, 0)^T\),

\(G.\mathcal{O}[F] = (g_{20}, g_{21}, 1)^T\).

Suponha ainda que conhecemos a coordenada de algum ponto \(P\) em relação a \(F\) , a saber \(P[F ] = (\alpha_0 , \alpha_1 , \alpha_2)^T\). Sabemos que \(\alpha_2 = 1\) já que \(P\) é um ponto, mas vamos deixá-lo como variável para obter uma expressão que funcione também para vetores livres.

Nosso objetivo é determinar \(P[G] = (\beta_0 , \beta_1 , \beta_2)^T\). Portanto, os valores de \(\beta_i\) devem satisfazer:

\(P = \beta_0 G.e_0 + \beta_1 G.e_1 + \beta_2 G.\mathcal{O}\).

Essa é uma expressão em geometria afim que podem ser expressas com relação ao sistema padrão \(F\) da seguinte forma:

\(\begin{pmatrix}\alpha_0 \\ \alpha_1 \\ \alpha_2\end{pmatrix} = \beta_0 \begin{pmatrix}g_{00} \\ g_{01} \\ 0\end{pmatrix} + \beta_1 \begin{pmatrix}g_{10} \\ g_{11} \\ 0\end{pmatrix} + \beta_2 \begin{pmatrix}g_{20} \\ g_{21} \\ 1\end{pmatrix} = \begin{pmatrix}g_{00} & g_{10} & g_{20} \\ g_{01} & g_{11} & g_{21} \\ 0 & 0 & 1\end{pmatrix} \begin{pmatrix}\beta_0 \\ \beta_1 \\ \beta_2\end{pmatrix}\).

Seja \(M\) a matrix \(3\times3\) acima. Note que suas colunas são os elementos de base para \(G\), expressas como vetor de coordenadas em \(F\).

\(\begin{pmatrix}g_{00} & g_{10} & g_{20} \\ g_{01} & g_{11} & g_{21} \\ 0 & 0 & 1\end{pmatrix} = \begin{pmatrix} G.e_0[F] \;\; \mid \;\; G.e_1[F] \;\; \mid \;\; G.\mathcal{O}[F] \end{pmatrix}\).

Portanto, dado \(P[G] = (\beta_0, \beta_1, \beta_2)^T\), podemos multiplicar \(M\) por \(P[G]\) para obter \(P[F] = (\alpha_0, \alpha_1, \alpha_2)^T\).

\(P[F] = M \cdot P[G]\)

Mas não é bem isso que queremos. Nós queremos obter \(P[G]\) em termos de \(P[F]\). Para isso, podemos calcular a inversa de \(M\), denotada por \(M^{-1}\). Vamos afirmar que, caso se trate de uma base válida, ou seja, com os vetores de base linearmente independentes, então a inversa existe e assim temos:

\(P[G] = M^{-1} \cdot P[F]\)

Essa inversa é simples de calcular por se tratar de uma matriz \(3\times3\). No entanto, no espaço 3D, as matrizes serão \(4\times4\) e a sua inversão é um pouco mais complexa.

10.7. Produto vetorial

O produto vetorial, também chamado de produto cruzado, é uma operação vetorial no espaço 3D. Ele pode ser usado para responder a seguinte pergunta:

Dado dois vetores, \(\vec{u}\) e \(\vec{v}\), linearmente independentes, calcule um terceiro vetor \(\vec{w}\) que seja ortogonal a \(\vec{u}\) e a \(\vec{v}\).

Produto Vetorial

Dados dois vetores no espaço 3D, \(\vec{u}\) e \(\vec{v}\), produto vetorial denotado por \(\vec{u} \times \vec{v}\) é definido pela seguinte fórmula:

\(\vec{u} \times \vec{v} = \begin{pmatrix} u_y v_z - u_z v_y\\ u_z v_x - u_x v_z\\ u_x v_y - u_y v_x \end{pmatrix}\), que pode ser derivada do determinante de \(\begin{vmatrix} \vec{e}_x & \vec{e}_y & \vec{e}_z \\ u_x & u_y & u_z \\ v_x & v_y & v_z \end{vmatrix}\),

onde \(\vec{e}_x\), \(\vec{e}_y\) e \(\vec{e}_z\) são 3 vetores de uma base ortonormal. A direção e sentido do vetor resultante segue a regra da mão direita como ilustrado na Figura Fig. 10.3.

Fig. 10.3 Sentido do produto vetorial aplicando a regra da mão direita. Fonte: Wikimedia Commons - Right hand rule cross product.

Observe que essa operação é muito útil na construção de sistemas de coordenadas com bases ortogonais.

O produto vetorial é geralmente definido em espaços lineares 3D, uma vez que se aplica a vetores e não a pontos. Por isso vamos ignorar a coordenada homogênea por hora, pois ela deve ser sempre zero. Observe que o produto vetorial é definido apenas para um par de vetores livres e apenas no espaço 3D.

10.7.1. Propriedades

O produto vetorial tem as seguintes propriedades importantes:

• Anticomutativo: \(\vec{u} \times \vec{v} = -(\vec{v} \times \vec{u})\)

  portanto \(\vec{u} \times \vec{u} = 0\), pois é igual a sua própria negação.

• Distributivo para soma: \(\vec{u} \times (\vec{v} + \vec{w}) = \vec{u} \times \vec{v} + \vec{u} \times \vec{w}\)

• Linear para multiplicação por escalar: \((\alpha \vec{u}) \times \vec{v} = \vec{u} \times (\alpha \vec{v}) = \alpha (\vec{u} \times \vec{v})\)

• Não associativo: \((\vec{u} \times \vec{v}) \times \vec{w} \neq \vec{u} \times (\vec{v} \times \vec{w})\)

  mas satisfaz a identidade de Jacobi:

  \(\vec{u} \times (\vec{v} \times \vec{w}) + \vec{v} \times (\vec{w} \times \vec{u}) + \vec{w} \times (\vec{u} \times \vec{v}) = 0\)

• Paralelismo: dois vetores não nulos \(\vec{u}\) e \(\vec{v}\) são paralelos se e somente se \(\vec{u} \times \vec{v} = 0\).

• Perpendicularidade: Dado dois vetores não nulos e linearmente independentes \(\vec{u}\) e \(\vec{v}\), então \(\vec{u} \times \vec{v}\) é perpendicular a \(\vec{u}\) e a \(\vec{v}\), orientado segundo a regra da mão direita.

• Fórmula de Lagrange: usada para simplificar o cálculo de vetores na física

  \(\vec{u} \times (\vec{v} \times \vec{w}) = \vec{v} (\vec{u} \cdot \vec{w}) - \vec{w} (\vec{u} \cdot \vec{v})\)

• Ângulo e área: O comprimento do produto vetorial está relacionado ao comprimento e ângulo entre os vetores. Em particular:

  \(|\vec{u} \times \vec{v}| = |u| |v| \mbox{sin} \theta\),

  onde \(\theta\) é o ângulo entre \(\vec{u}\) e \(\vec{v}\).

  O produto vetorial geralmente não é usado para calcular ângulos porque o produto escalar pode ser usado para calcular o cosseno do ângulo (em qualquer dimensão) e pode ser calculado de forma mais eficiente.

  Esse comprimento \(|\vec{u} \times \vec{v}|\) também é igual à área do paralelogramo cujos lados são dados por \(\vec{u}\) e \(\vec{v}\).

O produto vetorial é comumente usado em computação gráfica na geração de sistemas de coordenadas. Dados dois vetores de base de um sistema, é útil gerar um terceiro vetor que seja ortogonal aos dois primeiros. O produto vetorial faz exatamente isso. Também é útil para gerar normais de superfície. Dados dois vetores tangentes de uma superfície, o produto vetorial gera um vetor que é normal à superfície.

10.8. Orientação

Dados dois números reais \(P\) e \(Q\), há três maneiras possíveis de ordená-los:

• \(p < q\),
• \(p = q\) ou
• \(p > q\).

Podemos definir uma função de orientação, que assume os valores +1, 0 ou -1 em cada um desses casos. Ou seja,

\(\mbox{Or}_1(p, q) = \mbox{sign}(q - p)\),

onde \(\mbox{sign}(x)\) é -1, 0 ou +1 dependendo se \(x\) é negativo, zero ou positivo, respectivamente. Uma questão interessante é se é possível estender a noção de ordem para dimensões superiores.

A resposta é sim, mas em vez de comparar dois pontos, em geral podemos definir a orientação de \(d+1\) pontos no espaço \(d\)-dimensional. Definimos a orientação como o sinal do determinante consistindo em suas coordenadas homogêneas (com a coordenada homogênea dada primeiro). Por exemplo, no plano 2D, a orientação de três pontos \(P\), \(Q\) e \(r\) é definida como:

\(\mbox{Or}_2(p, q, r) = \mbox{sign det}\begin{pmatrix} 1 & 1 & 1\\ p_x & q_x & r_x \\ p_y & q_y & r_y\end{pmatrix}\),

e no espaço 3D, a orientação de quatro pontos \(P\), \(Q\), \(r\) e \(s\) é definida como:

\(\mbox{Or}_3(p, q, r, s) = \mbox{sign det}\begin{pmatrix} 1 & 1 & 1 & 1\\ p_x & q_x & r_x & s_x \\ p_y & q_y & r_y & s_y\\ p_z & q_z & r_z & s_z\end{pmatrix}\),

O que significa orientação intuitivamente?

A orientação de três pontos no plano é +1 se o triângulo \(PQR\) estiver orientado no sentido anti-horário, -1 se no sentido horário e 0 se todos os três pontos forem colineares, como ilustrado na Figura Fig. 10.4. No espaço 3D, uma orientação positiva significa que os pontos seguem um parafuso que gira segundo a orientação da “mão-direita”. Assim, se você visitar os pontos na ordem \(PQRS\), uma orientação positiva significa que você estaria “apertando” o parafuso, uma orientação negativa significa que você estaria soltando ou removendo o parafuso, e uma orientação zero significa que os pontos são coplanares. Observe que a ordem dos argumentos é importante. A orientação de \((p, q, r)\) é a negação da orientação de \((p, r, q)\). Tal como acontece com os determinantes, a troca de quaisquer dois elementos inverte o sinal da orientação.

Fig. 10.4 Orientação em 2 e 3 dimensões. Fonte: Figura 20 das notas de aula do Prof. Mount.

Você pode estar se perguntando por que colocar a coordenada homogênea primeiro?

A resposta que um matemático lhe daria é que essa é a posição onde essa coordenada deveria estar. Se você colocá-la por último, então as coisas orientadas positivamente são “destras” em dimensões pares e “canhotas” em dimensões ímpares. Ao colocá-lo em primeiro lugar, as coisas orientadas positivamente são sempre destras na orientação. Você não acha que assim é mais consistente e elegante? Colocar a coordenada homogênea por último parece ser uma convenção que surgiu na engenharia (sistemas gráficos) e foi adotada posteriormente pelas outras áreas que adotaram essas ferramentas. O valor do determinante em si é a área do paralelogramo definido pelos vetores \(q - p\) e \(r - p\), e portanto o determinante é também útil para calcular áreas e volumes.

10.9. Onde estamos e para onde vamos?

Nessa aula continuamos a recordar fundamentos da geometria e da álgebra linear que usaremos nesse curso, apresentando os conceitos de sistema de coordenadas, coordenadas homogêneas, o produto vetorial e suas propriedades.

Na próxima aula, vamos usar esses conceitos para aprender como representar e realizar transformações geométricas que facilitam a criação de desenhos e gráficos em geral.

10.10. Exercícios

1. Considere um array com 4 vértices \([p_0, p_1, p_2, p_3]\) que descreve um polígono de 4 lados no espaço 2D. Lembre-se que um polígono é convexo se todos seus ângulos internos forem menores ou iguais a \(180^o\). Assumindo que os vértices estão no array em ordem anti-horária, explique como usar os testes de orientação para determinar se o polígono é convexo ou não.

2. Considere um problema semelhante ao anterior, com um array de 4 vértices coplanares. Mas agora os vértices podem estar em ordem horária ou anti-horária, mas não sabemos qual. Explique como usar os testes de orientação para determinar se o polígono é convexo ou não.

3. Um problema importante na computação gráfica é determinar se há contato entre dois objetos. Para esse exercício, você pode usar, ou não, as seguintes informações para determinar se há contato entre duas elipses alinhadas aos eixos. Essas elipses são definidas pela seguinte equação:

   \((x - c_x)^2 / r_x^2 + (y - c_y)^2 / r_y^2 = 1\),

   onde \((c_x, c_y)\) é o centro da elipse e \((r_x > 0, r_y > 0)\) definem os raios da elipse. Observe que, caso \(r_x = r_y = r\), a equação se reduz a \((x-c_x)^2 + (y-c_y)^2 = r^2\), que é a equação de um círculo de raio \(r\).

   Considerando dois círculos de raios \(r_1\) e \(r_2\) centrados em \(c1=(c1_x, c1_y)\) e \(c2=(c2_x, c2_y)\) respectivamente, derive uma expressão que testa se esses dois círculos tem alguma sobreposição. Observe que não há sobreposição caso um círculo esteja inteiramente contido dentro do outro.

4. Considere um problema semelhante ao anterior, de determinar se há sobreposição entre duas elipses centradas em \(c1=(c1_x, c1_y)\) e \(c2=(c2_x, c2_y)\) e com raios \((r1_x, r1_y)\) e \((r2_x, r2_y)\), respectivamente. Assuma também que as duas elipses possuem a mesma razão de aspecto, definida por \(r_y / r_x\).

   Dica: há formas simples de resolver esses problemas sem usar a equação para círculo e elipse.

10.11. Para saber mais

• Aula 6 das notas de aula do Prof. Dave Mount
• Produto Vetorial na Wikipédia.
• Capítulo 4 do livro “Interactive Computer Graphics, 8th edition” de Angel e Shreiner.
• Capítulo 5 do livro “Computer Graphics - principles and practice”, Foley et al.