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

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

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

Псевдокод

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

Див. також Алгоритм Грехема Алгоритм Чена

Посилання Візуалізатор Реалізація на С++. Містить помилку в обрахунку векторного добутку. Виправлено у наведеному вище коді. Література