¿Por qué Graham y QuickHull a veces dan listas distintas de vértices?

Todos los puntos **extremos** yacen en la frontera de la envolvente convexa, pero si hay muchos puntos en **una misma recta** los algoritmos eligen de distinto modo cuáles dejar como **vértices** del polígono. Graham con el test **≤ 0** suele dejar solo los **extremos** del tramo colineal; QuickHull, sin un filtrado extra, puede incluir puntos **intermedios** en la arista. La **envolvente convexa** como conjunto en el plano coincide; cambia solo la representación poligonal.

¿Qué es la polilínea celeste en el modo Graham?

Es la **pila** actual de candidatos a vértices de la envolvente en el **paso** elegido: la envolvente parcial tras procesar el prefijo correspondiente de la lista ordenada. El **anillo rosa** es el punto que ahora se considera para incluir.

¿Qué tan estable es esto numéricamente?

Se usan **float64** ordinarios y productos cruz. Si los puntos casi coinciden o quedan casi alineados, la orientación puede «temblar»; al agregar puntos hay un pequeño **margen** respecto de los vecinos, para no crear duplicados accidentales.

¿Cómo parte QuickHull los puntos?

Tras elegir **L** y **R**, los puntos **estrictamente a la izquierda** de la recta orientada **LR** entran en la cadena **superior**, los **estrictamente a la derecha**, en la **inferior**. En cada paso, de los que quedan se elige el punto **C** **más alejado** de la arista actual **AB** (por el módulo del área orientada) y la recursión sigue con los conjuntos por fuera de los triángulos **ABC**, hasta que no queden puntos del lado exterior de la arista.

Envolvente convexa (Graham y QuickHull)

Puntos en el plano: barrido de Graham con animación paso a paso o QuickHull; comparación de los conjuntos de vértices.

Sobre el modelo

La envolvente convexa de un conjunto finito de puntos en el plano es el polígono convexo más pequeño que contiene todos los puntos; de modo equivalente, la intersección de todos los superconjuntos convexos. Hay dos construcciones clásicas de orden O(n log n). El barrido de Graham elige un punto de anclaje (el más bajo; si empatan en y, el más a la izquierda), ordena los demás por ángulo polar respecto del anclaje (si empatan en ángulo, por distancia) y recorre la lista manteniendo una pila: antes de agregar el siguiente punto se sacan de la pila vértices mientras la orientación de la última terna no sea estrictamente a la izquierda en el recorrido antihorario (en términos del producto cruz: se eliminan los casos cross ≤ 0, es decir, giro a la derecha o terna alineada). Los cuadros registran la pila y el punto «en consideración» para el paso a paso. QuickHull toma los extremos en x, L y R, parte el conjunto en puntos por encima y por debajo de la recta orientada LR y, en cada arista, agrega de forma recursiva el punto de mayor módulo del área orientada del triángulo (vía |cross|); los puntos sobre el segmento se descartan como interiores a la arista. Con colinealidades, distintas implementaciones pueden elegir distinto subconjunto de vértices en un mismo lado; la interfaz muestra si coinciden los conjuntos de índices de vértices de Graham y de QuickHull. Un clic en un sitio vacío agrega un punto (con protección frente a coincidencias casi exactas); arrastrar cerca de un punto lo mueve; el número de puntos y la semilla fijan una nube aleatoria.

Para quién: Matemática discreta y geometría computacional: construcción incremental y «divide y vencerás».

Conceptos clave

envolvente convexa
barrido de Graham
QuickHull
ordenación polar
pila monótona
orientación de una terna
divide y vencerás
colinealidad

Cómo funciona

La envolvente convexa es el polígono convexo más pequeño que contiene todos los puntos. Graham: punto de anclaje, ordenación polar, pila y prueba de giro vía cross; QuickHull: extremos en x, recursión por el punto más alejado de la arista (área ∝ |cross|). Las colinealidades pueden dar listas distintas de vértices con la misma envolvente.

Preguntas frecuentes

¿Por qué Graham y QuickHull a veces dan listas distintas de vértices?: Todos los puntos extremos yacen en la frontera de la envolvente convexa, pero si hay muchos puntos en una misma recta los algoritmos eligen de distinto modo cuáles dejar como vértices del polígono. Graham con el test ≤ 0 suele dejar solo los extremos del tramo colineal; QuickHull, sin un filtrado extra, puede incluir puntos intermedios en la arista. La envolvente convexa como conjunto en el plano coincide; cambia solo la representación poligonal.
¿Qué es la polilínea celeste en el modo Graham?: Es la pila actual de candidatos a vértices de la envolvente en el paso elegido: la envolvente parcial tras procesar el prefijo correspondiente de la lista ordenada. El anillo rosa es el punto que ahora se considera para incluir.
¿Qué tan estable es esto numéricamente?: Se usan float64 ordinarios y productos cruz. Si los puntos casi coinciden o quedan casi alineados, la orientación puede «temblar»; al agregar puntos hay un pequeño margen respecto de los vecinos, para no crear duplicados accidentales.
¿Cómo parte QuickHull los puntos?: Tras elegir L y R, los puntos estrictamente a la izquierda de la recta orientada LR entran en la cadena superior, los estrictamente a la derecha, en la inferior. En cada paso, de los que quedan se elige el punto C más alejado de la arista actual AB (por el módulo del área orientada) y la recursión sigue con los conjuntos por fuera de los triángulos ABC, hasta que no queden puntos del lado exterior de la arista.

Siga con temas cercanos de esta categoría — o todos los 85 de «Visualización matemática».

Toda la categoría →

NuevoEscuela

Curvas de Bézier y De Casteljau

Abrir el simulador

Los puntos de control fijan la curva de Bézier; el algoritmo de De Casteljau construye B(t) por interpolación lineal anidada.

NuevoEscuela

Triangulación de Delaunay y diagrama de Voronoi

Abrir el simulador

Triangulación de Bowyer–Watson y diagrama de Voronoi dual: el clic agrega sitios, arrastrar los mueve.

NuevoEscuela

Regresión lineal: MCO, ridge, lasso y R²

Abrir el simulador

Puntos en el plano y el modelo y = β₀ + β₁x: MCO ordinario, ridge (penalización L₂ sobre la pendiente) o lasso (penalización L₁). El desplazamiento Δy del punto con mayor |x| es un valor atípico de fuerte apalancamiento; se comparan SSE y R².

NuevoEscuela

K-medias (algoritmo de Lloyd)

Abrir el simulador

Puntos en el plano, número de clústeres k y centroides iniciales. Paso de Lloyd: asignar al centro más cercano y llevar el centroide al centro de masa. La demostración es una mezcla de gaussianas; suma de cuadrados intra-clúster.

NuevoEscuela

Descenso por gradiente (2D)

Abrir el simulador

Curvas de nivel de f(x, y) y trayectoria (x, y) ← (x, y) − η∇f; cuenco o pozo elíptico.

NuevoEscuela

Red de dos capas y retropropagación

Abrir el simulador

Dos características y una etiqueta binaria: capa oculta con tanh y salida logística. Gradiente completo de la entropía cruzada binaria media; mapa de calor de la probabilidad y frontera de nivel 0,5 (XOR o espirales).

Envolvente convexa (Graham y QuickHull)

Sobre el modelo

Cómo funciona

Preguntas frecuentes

Simuladores afines

Curvas de Bézier y De Casteljau

Triangulación de Delaunay y diagrama de Voronoi

Regresión lineal: MCO, ridge, lasso y R²

K-medias (algoritmo de Lloyd)

Descenso por gradiente (2D)

Red de dos capas y retropropagación

Envolvente convexa (Graham y QuickHull)

Sobre el modelo

Cómo funciona

Preguntas frecuentes