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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм Джарвіса (або алгоритм загортання подарунка) — алгоритм знаходження опуклої оболонки. Часова складність — О(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);
}

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Література[ред.ред. код]

  • Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. — М.: Мир, 1989. — 478 с. — ISBN 5-03-001041-6.