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

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

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

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

• Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. — М. : Мир, 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.