Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Выпуклая оболочка - алгоритм Джарвиса

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

    Очевидно, что искомый многоугольник будет являться выпуклым, и будет строиться из исходных точек.
    Идея алгоритма Джарвиса заключается в последовательном построении выпуклой оболочки. Сначала нам необходимо найти точку, которая должна быть в оболочке. Для этого можно взять самую нижнюю из самых левых точек. Далее будем каждый раз добавлять такую точку, чтобы угол образуемый следующей, текущей и предыдущей точками был максимален. Для этого совсем не обязательно находить сам угол. Мы можем использовать ориентированную площадь треугольника: пусть p0 - текущая точка, pn - уже выбранная следующая точка и pi - текущая точка в переборе точек, тогда если Sign Area Triangle (p0, pi, pn) > 0, то точка pi находится справа от вектора p0->pn и, значит, она составляет больший угол в выпуклой оболочке, поэтому мы ей дадим большее предпочтение, чем точке pn.
    Также нам необходимо рассмотреть вырожденный случай - все три точки (p0, pi, pn) лежат на одной прямой (ориентированная площадь треугольника равна 0). В таком случае нам нужно выбрать ту точку, которая расположена дальше от p0. Для этого тоже можно не использовать сложных вычислений, достаточно узнать, лежит ли pn в прямоугольнике с диагональю p0, pi (это делается простым сравнением координат точек). Если pn лежит в этом прямоугольнике, то pi лежит дальше от p0 и мы точке pi вследствии этого отдадим большее предпочтение, чем pn.

Сложность O(nk).
k - количество точек в оболочке
n - количество заданных точек


Листинг C++

void hull_jarvis (vector < point > p, vector < int > &ip)
{
    int n = p.size();
    int first, q, next, i;
    double sign;
    // находим самую нижнюю из самых левых точек
    first = 0;
    for (i = 1; i < n; ++ i)
        if (p[i].x < p[first].x || (p[i].x == p[first].x && p[i].y < p[first].y))
            first = i;
  
    q = first; // текущая точка
    // добавляем точки в оболочку
    do
    {
        ip.push_back(q);
        next = q;
        // ищем следующую точку
        for (i = n - 1; i >= 0; -- i)
            if (p[i].x != p[q].x || p[i].y != p[q].y)
            {
                sign = area_triangle (p[q], p[i], p[next]);

                if (next == q || sign > 0 || (sign == 0 && point_in_box (p[next], p[q], p[i])))
                    next = i;
            }
        q = next;
    }
    while (q != first);
}

21.06.2007, 15:59