Выпуклая оболочка алгоритм Грехема

Дано множество точек
Необходимо найти минимальный многоугольник, содержащий все эти точки

    Идея алгоритма Грехема заключается в последовательном отборе точек, упорядочённых ранее по полярному углу относительно какой-либо точки, которая обязательно будет входить в оболочку. Для этого можем использовать самую нижнюю из самых левых точек.
    Если посмотреть на полученный упорядочённый набор точек, то становится очевидно, что все точки, входящие в оболочку, будут распологаться в этом наборе в той же последовательности, в какой они образуют оболочку. Следовательно, мы можем последовательно их добавлять по одной из набора, но если получится, что в текущей оболочке три последовательные точки образуют угол больше либо равный 180 градусов (ориентированная площадь треугольника меньше либо равна нулю), то необходимо удалить предыдущую точку.
    Случай, когда две последовательные точки в оболочке лежат на одной прямой, можно не рассматривать отдельно, если в сортировке учесть, что чем дальше точка, тем она "приоритетнее".

Сложность O(nlogn).

Листинг C++

point first;
class less_of_ccw
{
public :
    bool operator () (point a, point b)
    {
        if (a.i == first.i) return true;
        if (b.i == first.i) return false;
        if (ccw (first, a, b)) return true;
        if (ccw (first, b, a)) return false;
        return dist (first, a) > dist (first, b);
    }
};
void hull_graham (vector < point > p, vector < int > &ip)
{
    int n = p.size();
    int i;
    for (i = 0; i < n; ++ i)
        p[i].i = i;
    // ищем самую нижнюю из самых левых точек - первая точка
    first = p[0];
    for (i = 1; i < n; ++ i)
        if (first.x > p[i].x || (first.x == p[i].x && first.y > p[i].y))
            first = p[i];

    // сортируем точки по по угла относительно первой точки
    sort (p.begin (), p.end (), less_of_ccw ());
    // первая точка оболочки
    ip.push_back (0);
    // ищем вторую точку оболочки
    for (i = 1; i < n && abs (area_triangle (p[0], p[1], p[i])) <= eps; ++ i);
    ip.push_back (1);

    // последовательно добавляем точки в оболочку
    int top = 1; // индекс последней точки в оболочке
    while (i < n)
    {
        // если угол больше pi то извлекаем последнюю точку из оболочки
        if (! ccw (p[ip[top - 1]], p[ip[top]], p[i]))
        {
            -- top;
            ip.pop_back ();
        }
        // иначе добавляем точку в оболочку
        else
        {
            ++ top;
            ip.push_back (i);
            ++ i;
        }
    }
    for (i = 0; i < ip.size(); ++ i)
        ip[i] = p[ip[i]].i;
}

19.06.2007, 19:41

По всем вопросам обращаться: rumterg@gmail.com