Алгоритм быстрой оболочки (Quick hull)

Рассмотрим алгоритм построения выпуклой оболочки, основанный на принципе разделяй и властвуй. По своей сути этот алгоритм является аналогом быстрой сортировки для задачи упорядочивания элементов в массиве. Отсюда такое название.

Вся представленная реализация основана на описании с wikipedia. Оттуда же можно узнать смысл таинственных переменных S1 и подобных. В качестве “подопытной задачи” была выбрана все та же 5D. Выпуклая оболочка из сборника задач Меньшикова.

Итак пошагово рассмотрим алгоритм.
На начальном этапе мы имеем множество точек на плоскости

Неплохо. Находим самую левую(Л) и самую правую(П) точки из представленных. Если существует несколько самых левых или самых правых точек – то берем любую из них.

Формируем списки точек S1, лежащий выше прямой ЛП, и список точек S2, находящихся ниже ЛП.
Теперь наша задача построить выпуклую оболочку для верхней полуплоскости(S1) и нижней(S2), а затем грамотно их объединить в одну.
Все вышеизложенное можно можно закодировать следующим фрагментом:

1. void QuickHull(const vector<point> &vertex, vector<int> &convexHull)
2. {
3.   // нельзя построить выпуклую оболочку
4.   if (vertex.size() < 3)
5.     return;
6.   // поиск самой левой и самой правой точки
7.   int leftPos = 0, rightPos = 0;
8.   for (size_t i=1;i<vertex.size();i++)
9.   {
10.     if (Less(vertex[i].x, vertex[leftPos].x))
11.       leftPos = i;
12.     else if(Less(vertex[rightPos].x, vertex[i].x))
13.       rightPos = i;
14.   }
15.  
16.   line LR(vertex[leftPos],vertex[rightPos]);
17.   vector<int> S1; // точки выше прямой LR
18.   vector<int> S2; // точки ниже прямой LR
19.   for (size_t i=0;i<vertex.size();i++)
20.   {
21.     if (i != leftPos && i != rightPos)
22.     {
23.       if (LR.isLeft(vertex[i]))
24.         S1.push_back(i);
25.       else if (LR.isRight(vertex[i]))
26.         S2.push_back(i);
27.     }
28.   }
29.   QuickHull(vertex, convexHull, leftPos, rightPos, S1);
30.   QuickHull(vertex, convexHull, rightPos, leftPos, S2);
31. }

* This source code was highlighted with Source Code Highlighter.

Как видно из кода функция принимает на вход два параметра: набор точек(vertex) и контейнер(convexHull), который должен содержать индексы точек, образующих выпуклую оболочку, по завершению работы функции. Эти индексы соответствуют индексам точек из массива vertex.
В конце функции есть два однотипных вызова рекурсивной функции, которая строит выпуклую оболочку сначала для набора точек S1(строчка 29), затем для набора точек S2(строчка 30)

Рассмотрим, как ведет себя функция для набора точек S1.
Сначала находим точку TOP, входящую в набор S1, такую, что площадь треугольника (Л-TOP-П) максимальна. Если таких точек несколько нужно взять самую левую. Как можно догадаться, точка TOP будет максимально удаленной от прямой ЛП. Точка TOP точно входит в выпуклую оболочку.
Затем получаем набор точек S11, лежащий левее прямой Л-TOP и набора точек S12, находящихся левей прямой TOP-П.

Далее мы повторяем все что проделали для набора точек S1 относительно прямой ЛП для S11 и S12. Не привожу в посте полный код рекурсивной функции, т.к. он довольно большой.

Терминальным условием для рассматриваемой рекурсивной функции будет тот факт, что передаваемое множество точек, которое оказалось левее прямой на предыдущем шаге, пусто.
Для нижней половины алгоритм работает идентично 
 
Сложность данного алгоритма в среднем случае O(N*logN), но в худшем случае, когда набор точек образует выпуклую оболочку сложность становится квадратичной.

Полный код QuickHull для задачи 5D смотрите здесь