Алгоритм Джарвіса

Алгоритм Джарвіса (або алгоритм загортання подарунка) — алгоритм знаходження опуклої оболонки. Часова складність — О(n * h), де n — кількість точок, h — кількість точок опуклої оболонки. Тобто, алгоритм найбільш ефективний у випадку малої кількості точок опуклої оболонки.

Опис алгоритму

Нехай шукана опукла оболонка множини $P=\{p_{1},p_{2},...p_{n}\}$ точок. Як початкову беремо найлівішу точку (точку з найменшою x-координатою), якщо їх буде декілька, то виберемо серед них найнижчу (точку з найменшою y-координатою). Нехай знайдена точка — точка $p_{1}$ (її можна знайти за час $O(n)$ звичайним проходом по всіх точках і порівнянням координат). Точка $p_{1}$ напевно є вершиною опуклої оболонки. Далі для кожної точки $p_{i}$ шукаємо проти годинникової стрілки точки $p_{i+1}$ шляхом знаходження за $O(n)$ серед точок, що залишились, (включно з $p_{1}$) точку з найменшим полярним кутом $p_{i-1}p_{i}p_{i+1}$. Вона і буде наступною вершиною опуклої оболонки. При цьому не обов'язково обчислювати кут — достатньо обчислити векторний добуток (узагальненням векторного добутку для двовимірного випадку є псевдоскалярний добуток) між векторами $p_{i}p'_{i+1}$ та $p_{i}p''_{i+1}$, де $p'_{i+1}$ — знайдений на даний момент мінімум, $p''_{i+1}$ — претендент (першим мінімумом може бути обрана довільна точка). Якщо векторний добуток від'ємний, то знайдено новий мінімум. Якщо рівний нулю, тобто $p'_{i+1}$ та $p''_{i+1}$ лежать на одній прямій, то мінімум — та, яка лежить далі від точки $p_{i}$. Алгоритм продовжує роботу доки $p_{i+1}\neq p_{1}$. Чому алгоритм зупиниться? Тому, що точка $p_{1}$ (найнижча серед найлівіших точок) у будь-якому випадку належить до точок опуклої оболонки.

Псевдокод

Jarvis(P)
    1) p[1] = найнижча серед найлівіших точок множини P;
    2) i = 1;
    3) do:
         p[i+1] = довільна точка з P (крім вже зарахованих до опуклої оболонки, але включно з p[1]);
             (a)for (для кожної точки j з P, крім вже зарахованих до опуклої оболонки, але включно з p[1]
                 p[i+1] = min_polar_angle(p[i+1], P[j]); // мінімум через векторний добуток
             (b)i = i + 1;
       while p[i] != p[1]
    4) return p;

Реалізація на С++

 
//Point - some type that has x, y members and
//for which operator != is defined
template <typename Point>
inline bool determinantSignum(const Point& a,
                              const Point& b,
                              const Point& c)
{
    return (((b.x - a.x) * (c.y - b.y) -
             (c.x - b.x) * (b.y - a.y)) >= 0);
}

template <typename Point>
void jarvis(const std::vector<Point> & source,
            std::vector<Point>& result)
{
    if (source.empty())
    {
        return;
    }

    std::vector<Point> src = source;
    typedef typename std::vector<Point>::iterator PointIterator;
    PointIterator leftDownIt = src.begin();
    PointIterator it = leftDownIt + 1;
    Point currentPoint;
    Point leftDownPoint = *(leftDownIt);

    // Finding leftest lowest point

    for (PointIterator end = src.end(); it != end; ++it)
    {
        currentPoint = *it;
        if (currentPoint.x < leftDownPoint.x)
        {
            leftDownPoint = currentPoint;
            leftDownIt = it;
        }
        else if (currentPoint.x == leftDownPoint.x
                 && currentPoint.y < leftDownPoint.y)
        {
            leftDownPoint = currentPoint;
            leftDownIt = it;
        }
    }

    // Add selected point to answer
    src.erase(leftDownIt);
    result.push_back(leftDownPoint);

    currentPoint = leftDownPoint;

    Point nextPoint, tryPoint;
    PointIterator nextIt;

    do
    {
        nextPoint = leftDownPoint;
        nextIt = it;
        it = src.begin();
        for (PointIterator end = src.end(); it != end; ++it)
        {
            tryPoint = *it;
            if (determinantSignum(nextPoint,
                                  currentPoint,
                                  tryPoint))
            {
                nextPoint = tryPoint;
                nextIt = it;
            }
        }

        if (nextPoint != leftDownPoint)
        {
            src.erase(nextIt);
            result.push_back(nextPoint);
            currentPoint = nextPoint;
        }

    }
    while (nextPoint != leftDownPoint);
}

Див. також

• Алгоритм Грехема
• Алгоритм Чана

Посилання

• Візуалізатор
• Реалізація на С++. Містить помилку в обрахунку векторного добутку. Виправлено у наведеному вище коді. [Архівовано 6 липня 2012 у Wayback Machine.]

Література

• Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. — М. : Мир, 1989. — 478 с. — ISBN 5-03-001041-6.
• Jarvis, R. A. (1973). On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters. 2: 18—21. doi:10.1016/0020-0190(73)90020-3.