Introdução à Geometria Computacional
A geometria computacional é o ramo da ciência da computação dedicado ao estudo de algoritmos para resolver problemas espaciais. Como os computadores não processam formas visuais complexas diretamente, as soluções baseiam-se fortemente na geometria analítica, transformando entidades geométricas em coordenadas cartesianas e equações algébricas.
Retas e Colinearidade
Uma reta no plano cartesiano pode ser representada de diversas formas: equação reduzida, equação ponto-inclinação, equação segmentária e equação geral. Na equação reduzida ($y = mx + b$), $m$ representa o coeficiente angular (inclinação) e $b$ o coeficiente linear (intercepto). Dados dois pontos $(x_1, y_1)$ e $(x_2, y_2)$, a inclinação é calculada por $m = \frac{y_2 - y_1}{x_2 - x_1}$. É crucial notar que retas verticais (paralelas ao eixo $y$) não possuem inclinação definida e, portanto, não podem ser representadas pela equação reduzida.
Exemplo Prático: Máximo de Pontos Colineares
Dado um conjunto de pontos no plano, o objetivo é encontrar o número máximo de pontos que pertencem à mesma reta. Uma abordagem ingênua testaria todas as combinações de retas e contaria os pontos, resultando em complexidade $O(N^3)$. Uma otimização clássica consiste em fixar um ponto pivô, calcular a inclinação em relação a todos os outros pontos e utilizar uma estrutura de dados para agrupar inclinações idênticas. Para evitar erros de precisão com números de ponto flutuante, a inclinação pode ser representada como uma fração irredutível $(dy, dx)$ dividida pelo máximo divisor comum (MDC).
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
struct Point {
int x, y;
};
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int maxCollinearPoints(const std::vector<Point>& points) {
int n = points.size();
if (n <= 2) return n;
int maxPoints = 2;
for (int i = 0; i < n; ++i) {
std::map<std::pair<int, int>, int> slopes;
for (int j = 0; j < n; ++j) {
if (i == j) continue;
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int g = gcd(std::abs(dx), std::abs(dy));
dx /= g;
dy /= g;
if (dx < 0) {
dx = -dx;
dy = -dy;
} else if (dx == 0) {
dy = std::abs(dy);
}
slopes[{dx, dy}]++;
}
for (const auto& pair : slopes) {
maxPoints = std::max(maxPoints, pair.second + 1);
}
}
return maxPoints;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
if (!(std::cin >> n)) return 0;
std::vector<Point> pts(n);
for (int i = 0; i < n; ++i) {
std::cin >> pts[i].x >> pts[i].y;
}
std::cout << maxCollinearPoints(pts) << "\n";
return 0;
}
Triângulos e Posicionamento de Pontos
Ao posicionar um triângulo $\triangle ABC$ no plano cartesiano com vértices $(x_A, y_A)$, $(x_B, y_B)$ e $(x_C, y_C)$, podemos analisar suas propriedades métricas e topológicas.
Área do Triângulo
A Fórmula de Heron permite calcular a área através dos comprimentos dos lados: $S = \sqrt{p(p-a)(p-b)(p-c)}$, onde $p$ é o semiperímetro. No entanto, em geometria computacional, é frequentemente mais eficiente e numericamente estável utilizar o produto vetorial (cross product). A área é dada por metade do valor absoluto do produto vetorial entre os vetores formados pelos lados do triângulo.
Relação Ponto-Triângulo
Para determinar a posição de um ponto $P$ em relação ao $\triangle ABC$:
- No vértice ou na aresta: $P$ coincide com um dos vértices ou o produto vetorial entre $P$ e uma das arestas é zero.
- No interior: A soma das áreas dos triângulos $\triangle ABP$, $\triangle ACP$ e $\triangle BCP$ é exatamente igual à área de $\triangle ABC$. Alternativamente, os produtos vetoriais das arestas em relação a $P$ possuem o mesmo sinal.
- No exterior: A soma das áreas dos sub-triângulos é estritamente maior que a área do triângulo original, ou os sinais dos produtos vetoriais são mistos.
Exemplo Prático: Classificação de Ponto no Triângulo
O problema exige classificar a posição de um ponto $P$ em relação a um triângulo. O código abaixo utiliza a abordagem do produto vetorial, que é mais robusta e evita chamadas à função de raiz quadrada, mitigando erros de precisão de ponto flutuante.
#include <iostream>
#include <cstdio>
struct Point {
double x, y;
};
double crossProduct(const Point& O, const Point& A, const Point& B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int main() {
Point A, B, C, P;
if (scanf(" (%lf,%lf)", &A.x, &A.y) != 2) return 0;
scanf(" (%lf,%lf)", &B.x, &B.y);
scanf(" (%lf,%lf)", &C.x, &C.y);
scanf(" (%lf,%lf)", &P.x, &P.y);
double d1 = crossProduct(P, A, B);
double d2 = crossProduct(P, B, C);
double d3 = crossProduct(P, C, A);
bool has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
bool has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
if (d1 == 0 || d2 == 0 || d3 == 0) {
if ((P.x == A.x && P.y == A.y) || (P.x == B.x && P.y == B.y) || (P.x == C.x && P.y == C.y)) {
std::puts("4"); // Vértice
} else {
std::puts("3"); // Aresta
}
} else if (has_neg && has_pos) {
std::puts("2"); // Exterior
} else {
std::puts("1"); // Interior
}
return 0;
}
Círculos
A equação reduzida de um círculo com centro $P(x_P, y_P)$ e raio $r$ é $(x - x_P)^2 + (y - y_P)^2 = r^2$. As relações de posição entre pontos, retas e círculos seguem os mesmos princípios da geometria analítica clássica, baseando-se na comparação entre a distância do centro à entidade e o raio $r$.
Envoltória Convexa (Convex Hull)
Um conjunto de pontos no plano é considerado convexo se, para quaisquer dois pontos pertencentes ao conjunto, o segmento de reta que os une está inteiramente contido dentro do próprio conjunto.
A envoltória convexa (ou Convex Hull) de um conjunto de $n$ pontos é o menor polígono convexo que contém todos os pontos do conjunto. Visualmente, pode ser imaginada como o formato assumido por um elástico esticado que envolve todos os pontos e é solto até ficar justo. Algoritmos como Graham Scan e Monotone Chain são frequentemente empregados para compuatr a envoltória convexa em tempo $O(N \log N)$.