Înfășurătoarea convexă — elasticul din jurul punctelor

Ce e înfășurătoarea convexă

Pentru o mulțime de puncte în plan, înfășurătoarea convexă (convex hull) este cel mai mic poligon convex care le conține pe toate. Un poligon e convex dacă, mergând pe contur într-un singur sens, virezi mereu în aceeași direcție — nu are nicio adâncitură.

Punctele care contează sunt doar cele de pe margine; cele din interior sunt „ascunse”. Intuiția cheie e cotitura la stânga: dacă parcurgi conturul în sens trigonometric (invers acelor de ceas), la fiecare vârf trebuie să virezi spre stânga. Dacă într-un vârf ai vira la dreapta sau ai merge drept, acel vârf creează o adâncitură și trebuie eliminat.

Cum decizi în ce parte virezi fără unghiuri sau numere reale? Cu produsul vectorial. Pentru trei puncte O, A, B, valoarea (A - O) x (B - O) are semnul:

• pozitiv → virezi la stânga (sens trigonometric);
• zero → cele trei puncte sunt coliniare;
• negativ → virezi la dreapta.

Folosim doar semnul, niciodată valori reale, deci totul rămâne pe întregi.

Algoritmul Andrew (monotone chain)

Algoritmul lui Andrew construiește înfășurătoarea în doi pași simetrici:

1. Sortează toate punctele după x, iar la x egal după y. Acum primul punct e cel mai din stânga, ultimul e cel mai din dreapta.
2. Construiește învelișul inferior: parcurgi punctele de la stânga la dreapta și le pui pe o stivă. Înainte de a adăuga un punct nou, cât timp ultimele două din stivă plus punctul nou nu formează o cotitură la stânga, scoți vârful stivei (pop).
3. Construiește învelișul superior: la fel, dar parcurgi punctele invers, de la dreapta la stânga.
4. Lipești cele două lanțuri. Împreună înconjoară complet mulțimea de puncte.

Stiva ține lanțul curent. Produsul vectorial e arbitrul care decide dacă vârful stivei produce o cotitură greșită și trebuie aruncat. Fiecare punct intră o dată și iese cel mult o dată, deci construcția e liniară — O(n). Costul total e dat de sortare: O(n log n).

Exemplu pas cu pas

Fie punctele: (0,0), (1,1), (2,0), (2,2), (0,2). Sortate după (x, y) devin: (0,0), (0,2), (1,1), (2,0), (2,2).

Construim învelișul inferior (stiva crește de la stânga):

• adaugă (0,0) → stiva [(0,0)]
• adaugă (0,2) → stiva [(0,0), (0,2)]
• vrei (1,1): (0,0)→(0,2)→(1,1) virează la dreapta, deci pop (0,2); stiva [(0,0)], apoi adaugă (1,1) → [(0,0), (1,1)]
• vrei (2,0): (0,0)→(1,1)→(2,0) virează la dreapta, deci pop (1,1); stiva [(0,0)], apoi adaugă (2,0) → [(0,0), (2,0)]
• adaugă (2,2) → [(0,0), (2,0), (2,2)]

Observă cum punctul (1,1), aflat în interiorul pătratului, a fost scos: el nu face parte din contur. Învelișul superior se construiește simetric, parcurgând invers, și completează poligonul cu colțul (0,2).

Implementare C++

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

struct Punct {
    long long x, y;
};

// produs vectorial (A-O) x (B-O); semn: >0 stanga, =0 coliniar, <0 dreapta
long long cross(const Punct& O, const Punct& A, const Punct& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

bool operator<(const Punct& a, const Punct& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

vector<Punct> convexHull(vector<Punct> p) {
    int n = p.size();
    if (n < 3) return p;                 // prea putine puncte
    sort(p.begin(), p.end());            // sortare dupa (x, y): O(n log n)

    vector<Punct> hull(2 * n);
    int k = 0;                           // k = inaltimea stivei

    // invelisul inferior: stanga -> dreapta
    for (int i = 0; i < n; i++) {
        // pop cat timp nu virez la stanga (cotitura gresita)
        while (k >= 2 && cross(hull[k - 2], hull[k - 1], p[i]) <= 0) {
            k--;
        }
        hull[k++] = p[i];
    }

    // invelisul superior: dreapta -> stanga
    int jos = k + 1;                     // dimensiunea minima a invelisului inferior
    for (int i = n - 2; i >= 0; i--) {
        while (k >= jos && cross(hull[k - 2], hull[k - 1], p[i]) <= 0) {
            k--;
        }
        hull[k++] = p[i];
    }

    hull.resize(k - 1);                  // ultimul punct = primul, il scoatem
    return hull;
}

int main() {
    vector<Punct> p = {{0, 0}, {1, 1}, {2, 0}, {2, 2}, {0, 2}};
    vector<Punct> h = convexHull(p);

    cout << "Varfuri pe infasuratoare: " << h.size() << "\n";  // 4
    for (const Punct& q : h) {
        cout << "(" << q.x << ", " << q.y << ")\n";
    }
    // (1,1) lipseste: e in interior, nu pe contur
    return 0;
}

Aici vector<Punct> hull joacă rolul stivei: k e vârful, hull[k-1] e elementul de sus, iar k-- e operația de pop. Condiția cross(...) <= 0 elimină atât virajele la dreapta, cât și punctele coliniare (vezi mai jos de ce <= și nu <).

Complexitate

Construirea e liniară pentru că fiecare punct e adăugat o dată și scos cel mult o dată din stivă. Sortarea domină timpul total.

Vizualizare

Recapitulare

• Înfășurătoarea convexă e cel mai mic poligon convex care conține toate punctele — elasticul strâns în jurul cuielor de la margine.
• Algoritmul Andrew sortează după (x, y), apoi construiește învelișul inferior și cel superior cu o stivă, scoțând cotiturile greșite cu produsul vectorial.
• Complexitatea e O(n log n), dominată de sortare; ține produsul vectorial pe long long și decide coliniaritatea cu <= sau < după nevoie.