Geometria Computacional: Conceitos Básicos

Introdução Teórica

Geometria computacional exige cuidado com precisão (evitar float, preferir double ou inteiros quando possível) e robustez (casos degenerados como 3 pontos colineares).

Primitivas Fundamentais

  1. Vetores: Diferença entre dois pontos: \(\vec{AB} = B - A\).
  2. Produto Escalar (Dot Product): \(x_1x_2 + y_1y_2\). Útil para ângulos e projeção. Se zero, vetores são perpendiculares.
  3. Produto Vetorial (Cross Product): \(x_1y_2 - x_2y_1\).
    • Área: A magnitude é a área do paralelogramo formado. Área do triângulo = \(|CP|/2\).
    • Orientação: Indica se giramos para esquerda (positivo) ou direita (negativo) ao ir de \(\vec{u}\) para \(\vec{v}\). Fundamental para testar intersecções e polígonos.

Problema Clássico

Problema: Flores de Fogo Link: Beecrowd 1039

Descrição: Determinar se um círculo desenhado pelo caçador engloba completamente o círculo da flor.

Solução: Puramente distância Euclidiana. O círculo menor (raio \(R_2\)) está dentro do maior (\(R_1\)) se a distância entre centros + \(R_2 \le R_1\). \(dist = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\).

Variações e Exercícios

  1. [Área do Círculo]
  2. [Elevador]
    • Foco: Geometria básica e lógica de verificação de limites.
    • Link: Beecrowd 1124
  3. [Ponto em Polígono]
    • Não há link direto fácil no Beecrowd Intro, mas o conceito usa Cross Product para verificar se um ponto está sempre do mesmo lado das arestas (para convexos) ou Ray Casting (geral).
Back to top