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

Теория:   Wikipedia, Hardfire

Практика: Меньшиков – 5D [informatics.mccme.ru]

Визуализатор: rain.ifmo.ru [Java]

Реализация:
Алгоритм Джарвиса позволяет строить выпуклую оболочку на множестве заданных точек. Алгоритмическая сложность O(N*H), где N – общее количество точек, H – количество точек в выпуклой оболочке.

Для начала ознакамливаемся с теоретическим материалом(см. начало поста).

Рассмотрим два подхода к реализации данного алгоритма.
Первый подход: 
Приведу пример функции, реализующую основную логику:

1. void ConvexHullJarvis(const vector<point> &mas, vector<int> &convex_hull)
2. {
3.   // находим самую левую из самых нижних
4.   int base = 0;
5.   for (int i=1;i<n;i++)
6.   {
7.     if (mas[i].y < mas[base].y)
8.       base = i;
9.     else
10.       if (mas[i].y == mas[base].y &&
11.         mas[i].x < mas[base].x)
12.         base = i;
13.   }
14.   // эта точка точно входит в выпуклую оболочку
15.   convex_hull.push_back(base);
16.  
17.   point first = mas[base];
18.   point cur = first;
19.   point prev = point(first.x - 1, first.y);
20.   do
21.   {
22.     double minCosAngle = 1e9; // чем больше угол, тем меньше его косинус
23.     double maxLen = 1e9;
24.     int next = -1;
25.     for (int i=0;i<n;i++)
26.     {
27.       double curCosAngle = CosAngle(prev, cur, mas[i]);
28.       if (Less(curCosAngle,minCosAngle))
29.       {
30.         next = i;
31.         minCosAngle = curCosAngle;
32.         maxLen = dist(cur,mas[i]);
33.       }
34.       else if (Equal(curCosAngle, minCosAngle))
35.       {
36.         double curLen = dist(cur,mas[i]);
37.         if (More(curLen,maxLen))
38.         {
39.           next = i;
40.           maxLen = curLen;
41.         }
42.       }
43.     }
44.     prev = cur;
45.     cur = mas[next];
46.     convex_hull.push_back(next);
47.   }
48.   while (cur != first);
49. }

* This source code was highlighted with Source Code Highlighter.

Пояснения: вектор mas – содержит исходные точки. Вектор convex_hull содержит индексы точек исходного массива mas в заданном порядке обхода. Порядок обхода может быть по часовой или против часовой стрелки. В данной реализации ищется следующая точка, образующая с двумя последними точками выпуклой оболочки максимальный угол, поэтому порядок обхода будет против часовой стрелки:

Как видно из рисунка, на текущем шаге уже найдены три точки, образующие выпуклую оболочку. Это 2, 5 и 8. Следующая точка “i” должна образовывать максимальный угол 5-8-i. Интуитивно понятно, что это будет точка 4.
Сам угол при этом не ищется, а ищется только его косинус. Угол 5-8-i является углом в треугольнике. Значение угла варьируется в интервале [0,180] градусов. Мы помним, что косинус угла в этом интервале является монотонно убывающей функцей. Поэтому можем сделать вывод: чем больше угол, тем меньше его косинус. Этот момент описан в строчках 28-33.
Также не забываем обрабатывать вырожденный случай, когда имеется два претендента(точки A и B) на вакантное место быть следующей точкой в выпуклой оболочке. При этом последняя точка в выпуклой оболочке X и точки A,B лежат на одной прямой. В таком случае нужно выбрать ту точку, которая наиболее удалена от точки X. Этот момент описан в строчках 34-43.
В тот момент, когда следующая точка в выпуклой оболочке совпала с первой, можно сделать вывод, что выпуклая оболочка построена.

Данная реализация имеет ряд минусов. Во первых приходится работать с дробными числами, что влечет за собой написания специальных функций сравнения дробных чисел: Equal, More и Less. Также приходится вычислять расстояние между двумя точками(функция dist), что в свою очередь влечет использование функции взятия квадратного корня. Конечно можно было и не использовать квадратный корень, а считать длины в квадрате. От этого корректность алгоритма не меняется. Но есть способ еще лучше. Его мы рассмотрим во втором подходе.

По ссылке приведен полный исходный код этого подхода, который является решением задачи 5D. В этой задаче ищется периметр выпуклой оболочки.

Второй подход:
Суть второго подхода описана у команды HardFire.
Аналог функции, приведенной в первом подходе:

1. void ConvexHullJarvis(const vector<point> &mas, vector<int> &convex_hull)
2. {
3.   // находим самую левую из самых нижних
4.   int base = 0;
5.   for (int i=1;i<n;i++)
6.   {
7.     if (mas[i].y < mas[base].y)
8.       base = i;
9.     else
10.       if (mas[i].y == mas[base].y &&
11.         mas[i].x < mas[base].x)
12.         base = i;
13.   }
14.   // эта точка точно входит в выпуклую оболочку
15.   convex_hull.push_back(base);
16.  
17.   int first = base;
18.   int cur = base;
19.   do
20.   {
21.     int next = (cur + 1) % n;
22.     for (int i=0;i<n;i++)
23.     {
24.       int sign = OrientTriangl2(mas[cur], mas[next], mas[i]);
25.       // точка mas[i] находится левее прямой ( mas[cur], mas[next] )
26.       if (sign < 0) // обход выпуклой оболочки против часовой стрелки
27.         next = i;
28.       // точка лежит на прямой, образованной точками mas[cur], mas[next]
29.       else if (sign == 0)
30.       {
31.         // точка mas[i] находится дальше, чем mas[next] от точки mas[cur]
32.         if (isInside(mas[cur],mas[next],mas[i]))
33.           next = i;
34.       }
35.     }
36.     cur = next;
37.     convex_hull.push_back(next);
38.   }
39.   while (cur != first);
40. }

* This source code was highlighted with Source Code Highlighter.

Как видно теперь, работа идет в целых числах и для обработки вырожденного случая можно использовать функцию isInside, которая является менее тяжеловесной, чем функция dist.

Полный исходный код лежит: здесь