Envolvente convexa de puntos

La envolvente convexa es el polígono convexo más pequeño que contiene todos los puntos de un conjunto finito: el contorno de una goma elástica tensada alrededor de clavos en un tablero. Topógrafos, analistas SIG, desarrolladores de juegos y estudiantes de geometría computacional necesitan ese contorno a partir de muestras desordenadas: tracks GPS, huellas de edificios, vértices de sprites o nubes de clase de pares (x, y). Esta herramienta de envolvente convexa de puntos ejecuta el barrido de cadena monótona de Andrew: ordena los puntos por coordenada horizontal y luego vertical, construye las cadenas inferior y superior en pasadas lineales y devuelve los vértices extremos en sentido antihorario. Los puntos interiores y las muestras colineales a mitad de arista se eliminan solos. Puede enviar pares planos x/y o puntos geográficos lat/lon; el modo geo sigue calculando una envolvente plana en el plano longitud–latitud, la aproximación local habitual para sobres a escala de ciudad o de emplazamiento.

Qué es una envolvente convexa y cómo funciona la cadena monótona

Dado un conjunto finito de puntos en el plano, la envolvente convexa es el único conjunto convexo mínimo que los contiene a todos. Su frontera es un polígono convexo cuyos vértices son un subconjunto de la entrada: todo punto extremo que «sobresale» aparece en la envolvente, y todo punto que puede escribirse como combinación convexa de otros queda estrictamente dentro o sobre una arista. La cadena monótona de Andrew (también llamada barrido de cadena monótona) calcula esa frontera en tiempo O(n log n) dominado por la ordenación.

Tras ordenar por x creciente (y por y en empates de x), el algoritmo camina de izquierda a derecha para la envolvente inferior, manteniendo siempre un giro estricto a la izquierda en los tres últimos vértices de la pila; luego camina de derecha a izquierda para la envolvente superior con la misma prueba de giro.

Concatenar ambas cadenas sin duplicar los extremos compartidos más a la izquierda y más a la derecha produce la envolvente completa en sentido antihorario, empezando por el extremo más a la izquierda (y luego más abajo). Una prueba de giro no estricta (producto cruzado menor o igual que cero) elimina puntos colineales intermedios para que cada arista sea maximal.

Los conjuntos degenerados se tratan con claridad: un único punto devuelve una envolvente de un vértice; dos puntos distintos, un segmento de dos vértices; tres o más colineales, solo los dos extremos. Ese comportamiento coincide con las definiciones de aula del casco de puntos extremos y evita «muescas» de área nula en herramientas de polígono posteriores causadas por muestras a mitad de arista.

Contrato de entrada, modos de coordenadas y campos de respuesta

Cada registro puede ser {x, y} para trabajo plano, {lat, lon} para muestras geográficas, o un array de dos números. En modo auto, las claves lat/lon eligen etiquetado geográfico; x/y eligen etiquetado plano. El modo geo valida latitud en [−90, 90] y longitud en [−180, 180] y sigue ejecutando la envolvente en el plano lon–lat (x = longitude, y = latitude).

La precision opcional (0–15, predeterminado 10) fija los decimales de las coordenadas devueltas. El anillo de la envolvente está abierto: el primer vértice no se repite al final. Combine este extremo con calculadoras de área o perímetro solo cuando ya tenga un anillo ordenado; la salida de la envolvente ya está ordenada y lista para esas herramientas cuando necesite métricas del sobre de una nube de puntos en lugar de un polígono digitalizado a mano.

Dónde resulta útil un contorno convexo

Equipos de mapas y logística calculan el sobre convexo de paradas de reparto, pings de activos o hitos de topografía para dibujar un contorno exterior simple sin digitalizar a mano. Canalizaciones de juegos y CAD reducen proxies de colisión o cajas de selección de UI a la envolvente de vértices de malla o sprite para que las pruebas de solapamiento sigan siendo baratas.

Los cuadernos de ciencia de datos usan la envolvente como contorno exterior robusto para diagramas de dispersión y revisión de anomalías cuando un bounding box es demasiado holgado y una forma alfa cóncava es demasiado pesada. Plataformas de aula y concursos necesitan un oráculo determinista para ejercicios de «liste los puntos extremos en orden»; una capacidad parse pura devuelve coordenadas estables a precisión fija para que los calificadores no fallen por ruido flotante. La validación fallida no consume saldo.

Mantenga las nubes bajo el tope de diez mil puntos, fije los vértices de la envolvente en las pruebas y obtendrá sobres reproducibles para ETL SIG, workers de borde y deberes sin montar una biblioteca de geometría completa propia.