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

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

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

Нехай шукана опукла оболонка множини точок. Як початкову беремо найлівішу точку (точку з найменшою x-координатою), якщо їх буде декілька, то виберемо серед них найнижчу (точку з найменшою y-координатою). Нехай знайдена точка — точка (її можна знайти за час звичайним проходом по всіх точках і порівнянням координат). Точка напевно є вершиною опуклої оболонки. Далі для кожної точки шукаємо проти годинникової стрілки точки шляхом знаходження за серед точок, що залишились, (включно з ) точку з найменшим полярним кутом . Вона і буде наступною вершиною опуклої оболонки. При цьому не обов'язково обчислювати кут — достатньо обчислити векторний добуток (узагальненням векторного добутку для двовимірного випадку є псевдоскалярний добуток) між векторами та , де  — знайдений на даний момент мінімум,  — претендент (першим мінімумом може бути обрана довільна точка). Якщо векторний добуток від'ємний, то знайдено новий мінімум. Якщо рівний нулю, тобто та лежать на одній прямій, то мінімум — та, яка лежить далі від точки . Алгоритм продовжує роботу доки . Чому алгоритм зупиниться? Тому, що точка (найнижча серед найлівіших точок) у будь-якому випадку належить до точок опуклої оболонки.

Псевдокод

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.
  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.