// Eingabe: Menge von Punkten in der Ebene (P) // Ausgabe: Konvexe Huelle (H) void wrap (vector<Point2>& P, vector<Point2>& H) { // Finde den Startpunkt int left = 0; for (int i=1; i < P.size(); i++) if (P[i].x < P[left].x) left = i; // Einwickeln int p = left; // beginne mit linkestem Punkt int next = (left+1)%P.size(); // irgendein anderer Punkt do { H.push_back (P[p]); // Finde rechtesten Punkt for (int i=0; i < P.size(); i++) if (cw (P[p], P[next], P[i])) next = i; p = next; next = left; } while (p != left); }