Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM12 - Geometria Computacinal - Coggle Diagram
MM12 - Geometria Computacinal
Objetos geométricos básicos com bibliotecas
Pontos
Representação (x, y), operações: soma, subtração, escala, distância, comparação
Vetores como diferença entre pontos e uso de produto escalar e vetorial
Retas e segmentos
Representação por coeficientes ax + by + c = 0 ou por dois pontos
Testes: paralelas, coincidentes, interseção linha-linha, interseção segmento-segmento
Distância ponto-reta e distância ponto-segmento
Círculos
Representação centro + raio
Interseção círculo-círculo, tangência, arco e corda
Cálculos de arco, setor e área parcial
Triângulos
Área (Heron), incentro, circumcentro, circunferência inscrita e circunscrita
Relações trigonométricas e casos degenerados
Quadriláteros e polígonos simples
Tipos: retângulo, quadrado, trapézio, paralelogramo, losango
Fórmulas básicas de área e perímetro
Algoritmos em polígonos e rotinas úteis
Representação de polígono
Lista de vértices em ordem CW ou CCW, fechar polígono repetindo primeiro vértice
Perímetro
Soma das distâncias entre vértices consecutivos
Área (fórmula do determinante / shoelace)
Área assinada para distinguir orientação
Teste de convexidade
Usar sinais dos produtos vetoriais entre arestas consecutivas
Ponto dentro de polígono
Ray casting (paridade) ou soma de ângulos; cuidado com fronteira
Cortar polígono por reta
Construir polígono resultante mantendo pontos à esquerda e calculando interseções
Casos especiais a tratar
Colinearidade, vértices repetidos, polígonos concavos, pontos na fronteira
Cálculo do casco convexo
Definição: menor polígono convexo que contém todos os pontos
Algoritmos O(n log n)
Graham’s Scan
Escolher pivot, ordenar por ângulo, empilhar com teste ccw
Tratar colineares conforme especificação do problema
Andrew’s Monotone Chain
Ordenar por x (e y) e construir upper/lower, evita atan2
Uso prático
Envoltória para problemas de empacotamento, perímetro mínimo, simplificações
Complexidade típica O(n log n)