Un subconjunto S del plano es convexo si para cada par de puntos A, B en S, el segmento AB está completamente contenido en S.

Implementación de Algoritmos

Se presentan cuatro métodos para calcular la envolvente convexa:

1. Envoltura de Regalo (Gift Wrapping)

vector<Punto> envolturaRegalo(vector<Punto> puntos) {
    swap(puntos[0], *min_element(puntos.begin(), puntos.end(), compararX));
    vector<Punto> resultado;
    do {
        resultado.push_back(puntos[0]);
        swap(puntos[0], *min_element(puntos.begin() + 1, puntos.end(), ComparadorAngulo(puntos[0])));
    } while (puntos[0].x != resultado[0].x || puntos[0].y != resultado[0].y);
    return resultado;
}

2. Escaneo de Graham (Graham Scan)

vector<Punto> escaneoGraham(vector<Punto> puntos) {
    swap(puntos[0], *min_element(puntos.begin(), puntos.end(), compararX));
    sort(puntos.begin() + 1, puntos.end(), ComparadorAngulo(puntos[0]));
    vector<Punto> resultado = {puntos[0], puntos[1], puntos[2]};
    auto it = puntos.begin() + 3;
    while (it != puntos.end()) {
        while (resultado.size() > 1 && 
               zProductoVector(*(resultado.rbegin() + 1), resultado.back(), *it) >= 0) {
            resultado.pop_back();
        }
        resultado.push_back(*it++);
    }
    return resultado;
}

3. Cadena Monótona (Monotone Chain)

vector<Punto> cadenaMonotona(vector<Punto> puntos) {
    sort(puntos.begin(), puntos.end(), compararX);
    vector<Punto> inferior, superior;
    for (auto& p : puntos) {
        while (inferior.size() >= 2 && 
               zProductoVector(inferior[inferior.size()-2], inferior.back(), p) >= 0) {
            inferior.pop_back();
        }
        inferior.push_back(p);
    }
    for (auto it = puntos.rbegin(); it != puntos.rend(); ++it) {
        while (superior.size() >= 2 && 
               zProductoVector(superior[superior.size()-2], superior.back(), *it) >= 0) {
            superior.pop_back();
        }
        superior.push_back(*it);
    }
    inferior.insert(inferior.end(), superior.begin() + 1, superior.end() - 1);
    return inferior;
}

4. Cerco Rápido (QuickHull)

void cercoRapidoRec(const vector<Punto>& puntos, const Punto& a, const Punto& b, vector<Punto>& resultado) {
    if (puntos.empty()) return;
    float maxDist = 0;
    Punto pMax = puntos[0];
    for (auto& p : puntos) {
        float d = distanciaPuntoARecta(a, b, p);
        if (d > maxDist) {
            maxDist = d;
            pMax = p;
        }
    }
    vector<Punto> izquierda, derecha;
    for (auto& p : puntos) {
        if (zProductoVector(a, pMax, p) > 0) izquierda.push_back(p);
        if (zProductoVector(pMax, b, p) > 0) derecha.push_back(p);
    }
    cercoRapidoRec(izquierda, a, pMax, resultado);
    resultado.push_back(pMax);
    cercoRapidoRec(derecha, pMax, b, resultado);
}

vector<Punto> cercoRapido(vector<Punto> puntos) {
    Punto izquierda = *min_element(puntos.begin(), puntos.end(), compararX);
    Punto derecha = *max_element(puntos.begin(), puntos.end(), compararX);
    vector<Punto> arriba, abajo, resultado;
    for (auto& p : puntos) {
        if (zProductoVector(izquierda, derecha, p) > 0) arriba.push_back(p);
        else abajo.push_back(p);
    }
    resultado.push_back(izquierda);
    cercoRapidoRec(arriba, izquierda, derecha, resultado);
    resultado.push_back(derecha);
    cercoRapidoRec(abajo, derecha, izquierda, resultado);
    return resultado;
}

Funcoines Auxiliares

struct Punto {
    float x, y;
    Punto(float x, float y) : x(x), y(y) {}
};

float zProductoVector(const Punto& a, const Punto& b, const Punto& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool compararX(const Punto& a, const Punto& b) {
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}

float distanciaPuntoARecta(const Punto& a, const Punto& b, const Punto& p) {
    return abs((b.x - a.x)*(a.y - p.y) - (b.y - a.y)*(a.x - p.x)) / 
           sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y));
}

struct ComparadorAngulo {
    Punto pivote;
    ComparadorAngulo(Punto p) : pivote(p) {}
    bool operator()(const Punto& a, const Punto& b) {
        return zProductoVector(pivote, a, b) < 0;
    }
};