🟦 Envolvente Convexa

En la física de juegos 2D, la envolvente convexa de un polígono es su envoltorio convexo mínimo. Dos polígonos convexos pueden probarse para intersección usando el Teorema del Eje Separador (SAT): si existe una línea que separa las dos envolventes, no se solapan — y solo es necesario probar O(h₁ + h₂) ejes separadores candidatos (uno por arista). El algoritmo GJK (Gilbert-Johnson-Keerthi) extiende esto a 3D y maneja objetos curvos calculando la diferencia de Minkowski, logrando O(1) iteraciones en la práctica para formas simples. Tanto SAT como GJK son herramientas fundamentales en Unity, Bullet y otros motores de física.

Los puntos que están en una arista de la envolvente pero no son vértices (son colineales entre dos vértices de la envolvente) pueden incluirse o excluirse según la variante del algoritmo. El Graham scan estándar excluye los puntos interiores colineales (los elimina durante el paso de deduplicación de la ordenación), produciendo el conjunto mínimo de vértices. Algunas aplicaciones (por ejemplo, el cálculo del área de un polígono) prefieren incluir todos los puntos del borde. La elección afecta a h (tamaño de la envolvente), al tiempo de ejecución y al comportamiento de la prueba de orientación por producto cruzado (el producto cruzado cero debe manejarse con cuidado para evitar bucles infinitos en Jarvis march).

El algoritmo de Chan (Timothy Chan, 1996) logra un tiempo de O(n log h), donde h es el número de vértices de la envolvente — esto es óptimo porque generar h vértices toma Ω(h) tiempo y ordenar n puntos toma Ω(n log n). El enfoque de Chan estima h en fases de duplicación (probando h = 2, 4, 8, …), ejecutando un mini-Jarvis march que se detiene tras h pasos usando un Graham scan precalculado sobre n/h grupos de puntos como oráculos internos. Cuando la estimación coincide con el verdadero h, el algoritmo termina con una envolvente correcta. Cada fase cuesta O(n log h); la duplicación solo añade un factor constante, dando O(n log h) en total.

En programación lineal 2D, la región factible definida por m restricciones de desigualdad es un polígono convexo — una envolvente convexa de los puntos de intersección de las restricciones. La solución óptima de un programa lineal siempre se encuentra en un vértice del politopo factible. El método simplex recorre los vértices de este politopo; los métodos de punto interior recorren el interior. En dimensiones más altas (d variables, m restricciones), calcular la enumeración de vértices del politopo factible equivale a calcular una envolvente convexa en d dimensiones — un problema resuelto mediante algoritmos de doble descripción y de beneath-beyond.

En 3D, la envolvente convexa de n puntos es un poliedro convexo con como máximo O(n) vértices, aristas y caras (por la fórmula de Euler: V − E + F = 2, y para poliedros convexos F ≤ 2n − 4). Los algoritmos incluyen el Graham scan 3D (inserción incremental), divide y vencerás (O(n log n)), y la variante de empaquetado de regalo (Jarvis march en 3D). El algoritmo QuickHull3D de Barber, Dobkin y Huhdanpaa (1996, biblioteca qhull) es el estándar práctico — usado en ConvexHull de SciPy, MATLAB y herramientas de física de motores de juego.

Los puntos duplicados (coordenadas idénticas) deben tratarse explícitamente; la mayoría de las implementaciones deduplican la entrada antes de ejecutar el algoritmo de envolvente. En Graham scan, los puntos duplicados producirían productos cruzados de cero, causando ambigüedad en la ordenación angular. En Jarvis march, seleccionar un duplicado como el siguiente vértice de la envolvente podría causar un bucle infinito. Una implementación robusta elimina duplicados en un preprocesamiento de O(n log n), o usa aritmética exacta con perturbación (perturbación simbólica / SOS — simulación de simplicidad) para manejar todas las configuraciones degeneradas de forma consistente.

Existe una dualidad clásica: el diagrama de Voronoi 2D de n puntos es equivalente a la proyección de la envolvente convexa 3D de los mismos puntos elevados al paraboloide z = x² + y². Concretamente, se eleva cada punto (xᵢ, yᵢ) a (xᵢ, yᵢ, xᵢ² + yᵢ²), se calcula la envolvente convexa 3D, y luego se proyectan las caras de la envolvente inferior de vuelta a 2D — el resultado es la triangulación de Delaunay, y su grafo dual es el diagrama de Voronoi. Esto significa que cualquier algoritmo de envolvente convexa 3D de O(n log n) da inmediatamente un algoritmo de Voronoi de O(n log n), a la altura del clásico algoritmo de barrido de Fortune.

En las máquinas de vectores de soporte (SVM), el clasificador de margen máximo entre dos clases de puntos corresponde a encontrar los puntos más cercanos en las envolventes convexas de las dos clases — la dual de la "bola envolvente mínima". Los vectores de soporte de la SVM son exactamente los puntos de la envolvente más cercanos al hiperplano separador. Las envolventes convexas también aparecen en la profundidad de datos (profundidad de Tukey, el algoritmo de "pelado de cebolla"), la detección de anomalías (los puntos de datos fuera de la envolvente son valores atípicos), y en la optimización multiobjetivo, donde la frontera de Pareto es una porción de la envolvente convexa de los vectores objetivo factibles.