Problemas Diversos de Geometria Computacional

Escrito por Pedro Racchetti

Agora que aprendemos os fundamentos principais da geometria computacional, podemos passar a resolver alguns truques e problemas bastante conhecidos.

Rotacionar um vetor 2D por um ângulo $\theta$ :

Suponhamos um vetor $\overrightarrow{V}$ com coordenadas $a$ e $b$ . O vetor resultante $\overrightarrow{W}$ , da rotação de $\overrightarrow{V}$ por um ângulo $\theta$ no sentindo anti-horário, terá coordenadas:

$W_x = a cos(\theta) - b sen(\theta)$

$W_y = a sen(\theta) + b cos(\theta)$

Note que isso é equivalente a seguinte expressão, que utiliza o que é conhecido como matriz de rotação:

$\begin{bmatrix} W_x\\W_y\end{bmatrix} = \begin{bmatrix} cos(\theta) & -sin(\theta)\\sin(\theta) & cos(\theta)\end{bmatrix} \begin{bmatrix} a\\b\end{bmatrix}$

Segue a demonstração dessa solução:

Demonstração

Para facilitar as computações, usaremos a notação de vetores unitários, ou seja, entenderemos $\overrightarrow{V}$ como $a \hat{x} + b \hat{y}$ , como na figura 1.

Para se rotacionar o vetor $\overrightarrow{V}$ , teremos que rotacionar suas duas componentes (vertical e horizontal), pelo mesmo ângulo. Começaremos pela componente $\hat{x}$ : Após rotacionada, essa se tornará a componente $W_a$ do vetor $W$ . Como observamos na figura 2, $W_a$ é dada por $a cos(\theta) \hat{x} + a sen(\theta) \hat{y}$ , já que $W_a$ tem o mesmo módulo de $a$ .

Analogamente, para a componente $\hat{y}$ do vetor original, teremos como resultado a componente $W_b$ . Da mesma forma da outra componente, teremos o que mostra a figura 3, com $W_b$ sendo $-b sen(\theta) \hat{x} + b cos(\theta) \hat(y)$

Somando $W_a + W_b$ , teremos $\overrightarrow{W} = (a cos(\theta) - b sen(\theta)) \hat{x} + (a sen(\theta) + b cos(\theta) ) \hat{y}$ , como queríamos demonstrar.

[collapse]

Para melhor compreensão, aqui está o código de uma função para a struct de vetores que retorna o vetor rotacionado:

Encontrando a intersecção de dois segmentos de reta:

Outro problema bastante comum na programação competitiva é o de, dados dois segmentos de reta, $\overline{AB}$ e $\overline{CD}$ . descobrir se há intersecção entre eles, e se houver, qual é o ponto de intersecção.

Para descobrir se há intersecção, basta notar que, quando não houver, pelo menos um dos dois segmentos terá os dois pontos delimitadores do outro ao mesmo lado, e se isso não ocorrer, com certeza há intersecção. Para verificar isso, basta usar a regra da mão direita do produto vetorial, usando os segmentos como vetores.

Dado que há intersecção, para se encontrar o ponto $P$ de intersecção, podemos fixar a origem, sem perda de generalidade em $A$ , subtraindo o vetor $\overrightarrow{A}$ dos outros pontos. Agora, o vetor $\overrightarrow{P}$ terá a forma $\alpha \overrightarrow{B}$ , onde $\alpha$ é um coeficiente real, entre zero e um, e $P$ será colinear com $\overline{CD}$ . Nos resta agora encontrar $\alpha$ . Para isso, podemos usar busca-binária, já que se escolhermos um valor de $\alpha$ maior que o real, $P$ estará no mesmo lado de $B$ , em relação a $\overline{CD}$ , e quando for menor, estará do outro lado.

Ao encontrarmos $\alpha$ , encontramos $P$ , porém com $\overrightarrow{A}$ como origem, então deveremos somá-lo de volta aos pontos.

Segue o código, que lida com poucos corners (Lembre-se Geometria Computacional terá muitos corners diferente, que devem ser tratados de acordo com o problema)

Ponto dentro de Polígono Convexo

Outro problema importante de se saber resolver é o problema de verificar se um ponto se encontra dentro de um polígono, especialmente convexo.

Primeiro, note que para um ponto estar dentro do polígono, ele deve estar dentro do retângulo formado pelos pontos extremos, como mostrado na figura 4, pelas linhas tracejadas:

Além disso, iremos dividir o polígono em dois: o Upper Hull e o Lower Hull, como na Aula 3. Escolheremos qual dos dois usar de acordo com a posição do ponto relativa a diagonal que passado ponto extremo esquerdo e direito, mostrada na figura 5, sendo que se estiver acima (a esquerda) usaremos o Upper Hull, e caso contrário, o Lower Hull (se ele estiver na reta, com certeza está dentro do polígono).

Agora, basta encontrar o primeiro ponto do hull escolhido que está a direita (nesse caso, com coordenada no eixo x maior) do ponto sendo verificado com uma busca binária, e verificar se o ponto sendo verificado está a esquerda ou a direita do vetor formado pelo ponto encontrado e o antes dele no hull. Se estiver a esquerda, e o hull escolhido for o de cima, o ponto está fora do poligono, caso o contrário, está dentro. Se estiver a esquerda, e o hull escolhido for o de baixo, o ponto está dentro, e caso contrário, fora.

Esse algoritmo tem complexidade $O(log n)$ para cada ponto verificado, onde $n$ é o número de pontos do polígono.

Segue uma implementação do algoritmo exposto, aplicada ao problema Polygon:

Pratique!

Seguem alguns problemas para se colocar em prática as ideias explicadas: