Geometria Computacional Aula 1 - Pontos e Vetores

Escrito por Leonardo Paes, Thiago Mota e Lúcio Figueiredo

Um dos tipos de problemas recorrentes na programação competitiva são os problemas de geometria computacional. Geometria computacional é uma aplicação direta da geometria analítica na informática. Nessa aula, iremos estudar pontos e vetores no plano cartesiano, que são a base na geometria computacional.

Pontos

Pontos situados no plano cartesiano são representados por pares de inteiros $(x, y)$, normalmente chamados de coordenadas. Os pontos são adimensionais e podem representar inúmeras coisas como coordenadas em um mapa ou funções matemáticas como, por exemplo, $y = f(x)$.

A coordenada $x$ de um ponto $(x, y)$ é comumente chamada abscissa do ponto, e representa o deslocamento horizontal de tal ponto no plano. Já a coordenada $y$ é denominada ordenada do ponto, e representa o deslocamento vertical do ponto no plano.

No plano acima estão presentes os pontos $(x, y)$: $(1, 3)$ e $(2, 2)$. (Site utilizado: Desmos).

Em C++, iremos representar pontos usando o tipo pair, como representado no código abaixo:

Distância entre dois pontos

A distância entre dois pontos, mais conhecida como distância euclidiana, é definida como o tamanho da reta que liga os dois pontos. Para calcular a distância entre eles, podemos utilizar o Teorema de Pitágoras nas componentes $x$ e $y$.

Clique aqui para conferir a prova do Teorema de Pitágoras:

Observe o exemplo abaixo:

Imagine que queremos calcular a distância $d$ entre os pontos $(1, 3)$ (digamos, ponto $A$) e $(2, 2)$ (ponto $C$). Defina o ponto $B$ (ponto $(1, 2)$ na figura) como a interseção da reta horizontal que passa por $C$ com a reta vertical que passa em $A$.

Definindo $d_x$ como o comprimento do segmento ligando $B$ e $C$ e $d_y$ como o comprimento do segmento ligando $A$ e $B$, temos que $d_y = 3 - 2 = 1$ e $d_x = 2 - 1 = 1$. Como o triângulo formado ao ligar os pontos $A$, $B$ e $C$ é retângulo, podemos aplicar o Teorema de Pitágoras:

$\begin{cases} d^2 = d_x^2 + d_y^2 \\ d^2 = 1^2 + 1^2 \\ d^2 = 1 + 1 = 2 \\ d = \sqrt{2} \end{cases}$

Logo, a distância entre os pontos $A$ e $C$ é $\sqrt{2}$.

De modo geral, para dois pontos $A$ e $B$ de coordenadas $(A_x, A_y)$ e $(B_x, B_y)$, respectivamente, temos que $dist(A, B) = \sqrt{(A_x-B_x)^2 + (A_y-B_y)^2}$, onde $dist(A, B)$ é a distância entre os dois pontos.

O código a seguir calcula a distância entre dois pontos, utilizando a fórmula acima:

Obs: Em C++ , para pontos de distância $d$, normalmente é utilizado o $d^2$ ao invés do $d$, pois $d$ pode ser um número decimal (tipo double), e isso pode causar imprecisão na realização de cálculos.

Vetores

Um vetor é utilizado para representar grandezas vetoriais. Uma grandeza vetorial, diferentemente de um número, possuí módulo, direção e sentido. Observe a seguinte imagem:

O módulo do vetor é representado por seu tamanho, ou seja, a distância entre os dois pontos que representam o vetor. Já a direção é a reta que o vetor está localizado, então o vetor $\overrightarrow{AB}$ tem a mesma direção do vetor $\overrightarrow{BA}$; o que muda nesse caso é o sentido deles, já que um vai de $A$ pra $B$ e o outro de $B$ para $A$.

Normalmente representamos o vetor apenas como um ponto $(x, y)$, pois utilizamos a origem do vetor como sendo a origem do plano cartesiano $(0, 0)$, ou seja, o módulo do vetor representado pelo ponto é a distância entre os pontos $(0, 0)$ e $(x, y)$, o que deixa as contas bem mais simples. Quando a origem de um vetor dado não se localiza no ponto $(0, 0)$, precisaremos realizar uma translação no vetor, tópico abordado nas seções abaixo.

Soma e subtração de vetores

A soma de dois vetores $(x_1, y_1)$ e $(x_2, y_2)$ é representado pelo vetor da soma de suas coordenadas, ou seja, o vetor $(x_1 + x_2, y_1 + y_2)$. Como um exemplo, a soma dos vetores $(1, 3)$ e $(3, 2)$ é o vetor $(4, 5)$.

Um truque para somar dois vetores geometricamente é colocar um dos vetores com a origem na ponta do outro vetor e ligar a origem de um com a extremidade do outro. Observe a imagem:

Como podemos ver, o vetor $\vec{w}$ é a soma dos vetores $\vec{u}$ e $\vec{v}$. Aplicando o truque citado acima, obteremos a seguinte figura:

Ao colocar a origem do vetor $\vec{v}$ na extremidade do vetor $\vec{u}$, podemos ligar o início do vetor $\vec{u}$ com a extremidade do vetor $\vec{v}$, obtendo, assim, o vetor $\vec{w}$.

A subtração de vetores é definida de maneira semelhante à soma. O resultado da subtração de vetores $(x_1, y_1)$ e $(x_2, y_2)$ é o vetor $(x_1-x_2, y_1-y_2)$.

Para desenhar a subtração de dois vetores no plano, trataremos a subtração dos vetores $\vec{u}$ e $\vec{v}$ como sendo a soma do vetor $\vec{u}$ com o vetor $(-\vec{v})$, que possui mesmo módulo e direção que $\vec{v}$, com sentido contrário. Assim, realizaremos o mesmo truque da soma de vetores, invertendo o sentido do vetor $\vec{v}$.

Translação de vetores

Na seção de soma e subtração de vetores, assumimos que a origem de cada vetor se localizava no ponto $(0, 0)$; no entanto, este nem sempre é o caso. Para trabalhar com vetores com origens em pontos quaisquer, iremos mover, ou seja, transladar as suas origens para o ponto $(0, 0)$, mantendo os seus módulos, direções e sentidos.

Ao realizarmos a translação da origem do vetor $\vec{u}$ para $(0, 0)$, as coordenadas de sua extremidade irão ser alteradas. Portanto, o que queremos descobrir (de modo a manter as propriedades do vetor $\vec{u}$) são as coordenadas da sua extremidade após a translação.

Defina $(u_x, u_y)$ como as coordenadas da extremidade de $\vec{u}$ antes da translação e $(v_x, v_y)$ como as coordenadas da origem de $\vec{u}$. Como iremos levar o ponto $(v_x, v_y)$ para $(0, 0)$, notamos que a extremidade do vetor irá se deslocar em $-v_x$ no sentido horizontal e em $-v_y$ no sentido vertical, já que mantemos o módulo, a direção e o sentido de $\vec{u}$. Portanto, concluímos que as coordenadas da extremidade de $\vec{u}$ após a translação serão $(u_x - v_x, u_y - v_y)$. Desta forma, conseguimos uma maneira de trabalhar apenas com vetores de origem em $(0, 0)$.

A figura abaixo mostra o vetor $\vec{u}$ após a translação.