Алгоритм Грэхэма-Эндрю

Построение выпуклой оболочки, не должно занимать много времени. А надо признать, все приведенные мной реализации решения задачи построения выпуклой оболочки страдают большим объемом.

Реализация данного алгоритма на e-maxx’e порадовала свой лаконичностью.
Но увиденное у indy256 порадовала еще больше: 

1. vector<point> convexHull(vector<point> p) {
2.   int n = p.size();
3.   if (n <= 1)
4.     return p;
5.   int k = 0;
6.   sort(p.begin(), p.end());
7.   vector<point> q(n * 2);
8.   for (int i = 0; i < n; q[k++] = p[i++])
9.     for (; k >= 2 && !cw(q[k - 2], q[k - 1], p[i]); --k)
10.       ;
11.   for (int i = n - 2, t = k; i >= 0; q[k++] = p[i--])
12.     for (; k > t && !cw(q[k - 2], q[k - 1], p[i]); --k)
13.       ;
14.   q.resize(k - 1 - (q[0] == q[1]));
15.   return q;
16. }

* This source code was highlighted with Source Code Highlighter.

Очень крутая реализация =). Возьмем ее на вооружение, как и весь сайт indy256

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

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

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

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

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

Теория:   Wikipedia, Hardfire

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

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

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