Выпуклая оболочка

Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку O.
Сортируем остальные почки по полярному углу от O. Точка A должна идти раньше точки B, если поворот от вектора OA к вектору OB происходит против часовой стрелки (косое произведение положительно). Если OA и OB коллинеарны, то раньше идёт точка, ближайшая к O.
Добавляем точку O в оболочку.
Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.

struct Point {
    double x, y;

    Point() {}

    Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}

    bool operator < (const Point &that) const {
        return y < that.y || y == that.y && x < that.x;
    }

    double length() const {
        return hypot(x, y);
    }

    double crossProduct(const Point &that) const {
        return x * that.y - y * that.x;
    }
};

vector<Point> convexHull(vector<Point> &points) {
    nth_element(points.begin(), points.begin(), points.end());
    sort(points.begin() + 1, points.end(), [&](Point &a, Point &b) {
        Point &o = points[0], oa(o, a), ob(o, b);
        return oa.crossProduct(ob) > 0 || oa.crossProduct(ob) == 0 && oa.length() < ob.length();
    });

    vector<Point> hull;
    for (Point &p : points) {
        while (hull.size() >= 2) {
            Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1];
            Point ab(a, b), ap(a, p);
            if (ab.crossProduct(ap) <= 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(p);
    }
    return hull;
}

Ссылки

Теория:

e-maxx.ru — Построение выпуклой оболочки обходом Грэхэма
cp-algorithms.com — Convex Hull construction using Graham's Scan
algorithmica.org — Выпуклая оболочка: 1, 2
Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости
www.cs.princeton.edu/~cos226/lectures — 2.1 Elementary Sorts
usaco.guide — Convex Hull

Демонстрация:

VisuAlgo — Convex Hull

Код:

Задачи:

Выпуклая оболочка

Ссылки

Навигация

Поиск