Saltar a contenido

Convex hull#

Metadatos

Tipo: Algoritmo · Nivel: Experto · Dificultad: 5.5 · Complejidad: O(n log n)

Requisitos: Comparaciones 🏗️

La envolvente convexa de un conjunto de puntos es el menor polígono convexo que los contiene a todos (imagina una goma elástica que se cierra alrededor de los puntos). El algoritmo de cadena monótona de Andrew la calcula en O(n log n).

Puntos y su envolvente convexa
Los puntos naranjas forman la envolvente; los grises quedan dentro.

Idea#

Todo el algoritmo se apoya en una única operación: el producto vectorial (o producto cruz) en 2D. Dados tres puntos O, A y B, el signo de cross(O, A, B) indica la orientación del giro O -> A -> B:

  • > 0: giramos a la izquierda (sentido antihorario, CCW),
  • < 0: giramos a la derecha (sentido horario),
  • = 0: los tres puntos son colineales.

Primero ordenamos los puntos por coordenada x (y por y en caso de empate). Barriéndolos de izquierda a derecha construimos la cadena inferior y, de derecha a izquierda, la cadena superior; al unirlas obtenemos la envolvente completa en sentido antihorario. Ambas cadenas comparten los puntos con x mínima y máxima.

La envolvente separada en cadena inferior y superior
Los dos extremos en x dividen la envolvente en cadena inferior y superior.

Cada cadena se mantiene en una pila. Al añadir un punto nuevo, mientras los dos últimos vértices de la pila más el nuevo no formen un giro a la izquierda (cross <= 0), eliminamos el penúltimo: ese vértice quedaría "hundido" dentro de la envolvente o sobre una arista, así que no le pertenece. Como cada punto se apila y se desapila a lo sumo una vez, cada barrido es lineal.

El test <= 0 frente a < 0

Usar <= 0 (en lugar de < 0) descarta también los puntos colineales sobre una arista, dejando solo los vértices imprescindibles. Si necesitas conservar esos puntos intermedios, cambia la comparación a < 0.

Traza breve#

Tomemos los puntos del ejemplo: el cuadrado (0,0), (4,0), (4,4), (0,4) con un punto interior (1,1). Ordenados por x (y por y): (0,0), (0,4), (1,1), (4,0), (4,4).

En la cadena inferior, al llegar a (1,1) el giro (0,0) -> (0,4) -> (1,1) es a la derecha, así que se descarta (0,4); poco después (1,1) también cae al llegar (4,0), porque queda por encima del segmento (0,0)-(4,0). La cadena inferior queda como (0,0) -> (4,0) -> (4,4). La cadena superior añade (0,4) y, al cerrarse, vuelve a descartar el (1,1) interior. Resultado: los 4 vértices del cuadrado, justo lo que comprueba el ejemplo.

Código#

/**
 * Convex hull — Andrew's monotone chain.
 *
 * Computes the convex hull: the smallest convex polygon that contains a set of
 * 2D points (imagine a rubber band snapping around them).
 *
 * Input:  pts — a vector of 2D points (P{x, y}).
 * Output: the hull vertices in counter-clockwise order. Points lying *on* a hull
 *         edge (collinear) are dropped by the `<= 0` turn test, so only the
 *         corner vertices remain.
 * Complexity: O(n log n) time (dominated by the sort), O(n) space.
 */
#include <vector>
#include <algorithm>
using namespace std;

struct P {
    long long x, y;                          // 64-bit: cross() multiplies deltas
    bool operator<(const P& o) const {       // order the sweep by x, then by y
        return x < o.x || (x == o.x && y < o.y);
    }
};

// Cross product of vectors OA and OB. Its sign is the orientation of O->A->B:
//   > 0 left turn (counter-clockwise), < 0 right turn (clockwise), = 0 collinear.
long long cross(const P& O, const P& A, const P& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<P> convex_hull(vector<P> pts) {
    int n = pts.size();
    if (n < 3) return pts;                    // 0-2 points: nothing to build
    sort(pts.begin(), pts.end());             // left-to-right sweep order

    vector<P> hull;                           // grows/shrinks like a stack
    // Lower hull: sweep left -> right, keeping only left turns.
    for (int i = 0; i < n; i++) {
        // Drop the last vertex while the edge does not turn left (right or
        // collinear): such a vertex lies inside the hull or on an edge.
        while (hull.size() >= 2 &&
               cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    // Upper hull: sweep right -> left. `base` freezes the finished lower hull so
    // its vertices are never popped; pts[n-1] is skipped (already the last one).
    size_t base = hull.size() + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() >= base &&
               cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    hull.pop_back();     // the last point repeats the starting vertex — drop it
    return hull;
}

#include <vector>
#include <algorithm>
using namespace std;

struct P {
    long long x, y;
    bool operator<(const P& o) const {
        return x < o.x || (x == o.x && y < o.y);
    }
};

long long cross(const P& O, const P& A, const P& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<P> convex_hull(vector<P> pts) {
    int n = pts.size();
    if (n < 3) return pts;
    sort(pts.begin(), pts.end());

    vector<P> hull;
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 &&
               cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    size_t base = hull.size() + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() >= base &&
               cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    hull.pop_back();
    return hull;
}

#include <vector>
#include <algorithm>
using namespace std;
struct P {
    long long x, y;
    bool operator<(const P& o) const {
        return x < o.x || (x == o.x && y < o.y);
    }
};
long long cross(const P& O, const P& A, const P& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
vector<P> convex_hull(vector<P> pts) {
    int n = pts.size();
    if (n < 3) return pts;
    sort(pts.begin(), pts.end());
    vector<P> hull;
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 &&
               cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    size_t base = hull.size() + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() >= base &&
               cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    hull.pop_back();
    return hull;
}

"""Convex hull — Andrew's monotone chain.

Computes the **convex hull**: the smallest convex polygon that contains a set of
2D points (imagine a rubber band snapping around them). Points are ``(x, y)``
tuples. Points lying *on* a hull edge (collinear) are dropped, so only the corner
vertices remain; the result is returned in counter-clockwise order.

Complexity: O(n log n) time (dominated by the sort), O(n) space.
"""


def cross(o: tuple[int, int], a: tuple[int, int], b: tuple[int, int]) -> int:
    """Cross product of vectors OA and OB.

    Args:
        o, a, b (tuple[int, int]): 2D points.
    Returns:
        int: > 0 if O->A->B turns left (CCW), < 0 if it turns right, 0 if collinear.
    """
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def convex_hull(points: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Convex hull of a set of points (Andrew's monotone chain).

    Args:
        points (list[tuple[int, int]]): the input points.
    Returns:
        list[tuple[int, int]]: the hull vertices, in counter-clockwise order.
    """
    # Sort by (x, y) and drop duplicates; the sweep needs a left-to-right order.
    pts: list[tuple[int, int]] = sorted(set(points))
    if len(pts) < 3:
        return pts                       # 0-2 distinct points: nothing to build

    # Lower hull: sweep left -> right, keeping only left turns. We pop the last
    # vertex while the edge does not turn left (right turn or collinear point).
    lower: list[tuple[int, int]] = []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    # Upper hull: the same sweep in reverse builds the other half.
    upper: list[tuple[int, int]] = []
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    # Concatenate; drop each chain's last point (it repeats the other's start).
    return lower[:-1] + upper[:-1]

def cross(o: tuple[int, int], a: tuple[int, int], b: tuple[int, int]) -> int:
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def convex_hull(points: list[tuple[int, int]]) -> list[tuple[int, int]]:
    pts: list[tuple[int, int]] = sorted(set(points))
    if len(pts) < 3:
        return pts

    lower: list[tuple[int, int]] = []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    upper: list[tuple[int, int]] = []
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    return lower[:-1] + upper[:-1]

def cross(f, c, d):
    return (c[0] - f[0]) * (d[1] - f[1]) - (c[1] - f[1]) * (d[0] - f[0])
def convex_hull(h):
    i = sorted(set(h))
    if len(i) < 3:
        return i
    e = []
    for g in i:
        while len(e) >= 2 and cross(e[-2], e[-1], g) <= 0:
            e.pop()
        e.append(g)
    j = []
    for g in reversed(i):
        while len(j) >= 2 and cross(j[-2], j[-1], g) <= 0:
            j.pop()
        j.append(g)
    return e[:-1] + j[:-1]

Complejidad#

Recurso Coste
Tiempo O(n log n)
Memoria O(n)

El coste está dominado por la ordenación inicial (O(n log n)); los dos barridos son lineales, porque cada punto entra y sale de la pila a lo sumo una vez. La memoria es O(n) para almacenar los vértices de la envolvente.

Cuándo usarlo#

Es la base de muchos problemas de geometría: perímetro o área mínima que encierra los puntos, el par de puntos más lejano (diámetro), detección de puntos "extremos" o envolturas para colisiones, y como primer paso de técnicas como rotating calipers.

Cuándo NO usarlo#

  • Si necesitas conservar los puntos colineales de las aristas: usa < 0 en el test del producto vectorial en lugar de <= 0.
  • Con muy pocos puntos (< 3), donde la respuesta es trivial.
  • Si el problema no es de "envolvente" propiamente dicho: muchos problemas geométricos se resuelven con el producto vectorial directo, sin construir la envolvente completa.

Casos límite y errores comunes#

  • Menos de 3 puntos: no hay polígono; se devuelven los puntos tal cual.
  • Todos colineales: la "envolvente" degenera en el segmento entre los dos extremos (2 vértices).
  • Puntos duplicados: la versión en Python los elimina con set(...); la de C++ no los filtra, aunque el test <= 0 los trata igual que a los colineales. Si tu entrada puede traer duplicados y necesitas un recuento exacto, deduplica antes.
  • Desbordamiento: el producto vectorial multiplica diferencias de coordenadas; con coordenadas grandes usa enteros de 64 bits (long long), como aquí, para no desbordar.
  • Orientación: el signo del producto vectorial depende del sistema de ejes; con y hacia abajo (por ejemplo, en pantalla) izquierda y derecha se intercambian.

Referencias#