По книге Laszlo
"Вычислительная геометрия и компьютерная графика на С++"

Оболочка онлайн представляет собой специальный подход к поиску выпуклой оболочки для конечного набора точек S путем последовательного ввода по одной точке и поддержание выпуклой оболочки для всех точек, введенных до этого момента. Такую оболочку будем называть текущей оболочкой. Вначале текущая оболочка состоит из одной точки, принадлежащей S. По завершении ввода всех точек текущая оболочка становится эквивалентной выпуклой оболочке CH(S) и задача оказывается решенной.

При вводе каждой новой точки s в текущую оболочку могут возникнуть две ситуации. В первом случае точка s может принадлежать текущей оболочке (находиться на ее границе или внутри) и тогда текущую оболочку изменять не требуется. Во втором случае точка s лежит вне текущей оболочки и ее требуется модифицировать, как показано, например, на рис. 1.

Через точку s могут быть проведены две вспомогательные прямые линии, каждая из которых образует касательную к текущей оболочке. (Линия является касательной к выпуклому полигону Р, если она проходит через вершину Р и внутренняя область полигона Р полностью лежит по одну сторону от этой прямой линии). Левая (правая) касательная sr проходит через некоторую вершину l(r) текущей оболочки и лежит слева (справа) от текущей оболочки. Если наблюдатель находится в точке s и смотрит на выпуклую оболочку, то левая касательная будет видна слева, а правая касательная — справа.

Две вершины l и r, через которые проходят касательные, делят границу текущей оболочки на две цепочки вершин: ближняя цепочка, которая расположена ближе к точке s, и дальняя цепочка, которая находится дальше от точки s. (Ближняя цепочка расположена с той же стороны от отрезка прямой lr, что и точка s, дальняя цепочка располагается по другую сторону от отрезка lr). Для модификации текущей оболочки сначала необходимо найти две вершины l и r, определяющие границу между ближней и дальней цепочками. Затем мы должны удалить вершины ближней цепочки (за исключением вершин l и r) и внести точку s в нужном месте.

Следующая программа insertionHull возвращает текущую оболочку для массива s из п точек. Реализация использует классы из раздела 'Структуры геометрических данных'.

Point somePoint;         // global

Polygon *insertionHull (Point s[], int n}
{
  Polygon *p = new Polygon;
  p->insert(s[0]);
  for (int i = 1; i < n; i++) {
    if (pointInConvexPolygon(s[i], *p) ) continue;
    somePoint = s[i];
    leastVertex(*p, closestToPolygonCmp); // найти ближайшую вершину
                                          // второй аргумент - функция сравнения
    supportingLine (s[i], p, LEFT);
    Vertex *1 = p->v();
    supportingLine(s[i], p, RIGHT);
    delete p->split(l);                   // раcщепить многоугольник
    p->insert (s[i]);
  }
  return p;
}

На шаге i точка s[i] вносится в текущую оболочку р. Обращение к функции leastVertex перемещает окно полигона р на вершину, которая расположена ближе всего к точке s[i] . При этом осуществляется подготовка к последующему обращению supportingLine (s[i], р, LEFT) , переносящему окно на вершину t, через которую проходит левая касательная. При втором обращении к функции supportingLine окно перемещается на вершину r. Операция расщепления split применяется для удаления полигона р по его диагонали lr , отделяя таким образом ближнюю цепочку от дальней. Часть полигона, содержащая ближнюю цепочку, возвращается функцией split и удаляется. После этого точка s[i] вставляется в полигон р, который, после выполнения функции split, состоит только из дальней цепочки.

Рассмотрим функцию supportingLine более детально. Для определения вершины l, через которую проходит левая касательная, начнем с некоторой вершины в ближней цепочке и затем будем совершать обход по часовой стрелке вдоль текущей оболочки до тех пор, пока не дойдем до первой вершины v, последователь которой не лежит ни слева, ни после направленного отрезка прямой линии sv. Вершина v и будет вершиной l, которую мы ищем. Заметим, что если последователь для вершины v (например, вершина w) располагается за отрезком sv, то процесс поиска продолжается, поскольку вершина v не может быть крайней точкой, если она лежит между точками s и w.

При обращении к функции supportingLine в качестве аргументов задается полигон р, точка s вне полигона р и один из параметров типа перечисления LEFT или RIGHT (слева или справа), показывающий, какая из вершин (l или r) имеется в виду. Предполагается, что вершина, находящаяся в окне для полигона р, принадлежит ближней цепочке, что обеспечивается предварительным обращением к функции leastVertex. Функция перемещает окно полигона р на вершину, которую она находит (l или r):

void supportingLine (Point &s, Polygon *p, int side}
{
  int rotation = (side==LEFT) ? CLOCKWISE : COUNTER_CLOCKWISE;
  Vertex  *a = p->v();
  Vertex *b = p->neighbor(rotation);
  int с = b->classify(s, *a);
  while ( (c == side) || (c == BEYOND) | | (c == BETWEEN) ) {
    p—>advance(rotation);
    a = p->v();
    b = p->neighbor(rotation);
    с = b->classify(s, *a);
  }
}

Функция leastVertex, описанная в разделе о структурах данных, используется программой insertionHull для нахождения в полигоне р вершины, расположенной ближе всего к точке, хранящейся в глобальной переменной somePoint. Функция сравнения closestToPolygonCmp, вместе с которой вызывается функция leastVertex, сравнивает две точки и выбирает, какая из них находится ближе к точке somePoint:

int closestToPolygonCmp ( Point *a, Point *b}
{
  double distA = (somePoint - *a).length();
  double distB = (somePoint - *b).length();
  if (distA < distB) return -1;
  else if (distA > distB) return 1;
  return  0;
}

В процессе своей работы программа insertionHull может построить очень большую оболочку, которая к концу работы программы может оказаться полностью исключенной. Рассмотрим ситуацию, показанную на рис. 2а, когда в состав оболочки внесены все точки, кроме точек р, q и r. Включение каждой из этих последних трех точек приводит к исключению части ранее внесенной цепочки до тех пор, пока не останется один треугольник (рис. 2б-г). Очевидно, что если бы эти три точки р, q и r были внесены первыми, перед всеми остальными точками, то треугольная оболочка была бы сформирована с самого начала и внесение каждой из последующих точек было бы выполнено быстрее, так как потребовалось бы только определять, что точки находятся внутри треугольника. Таким образом, порядок включения точек может очень сильно влиять на эффективность.

Следует отметить, что стоимость выполнения операций по формированию выпуклой оболочки мало зависит от операций insert и split, используемых при включении и исключении точек в процессе отслеживания текущей оболочки. Кроме того, каждая точка может быть включена и исключена не более одного раза. Из этого следует, что общая цена операций insert и split при реализации алгоритма ограничена сверху величиной 0(n).

Аналогично и обращения к функции supportingLine сравнительно недорогие: оба обращения к ней на каждой итерации занимают время, пропорциональное длине ближней цепочки, затрачиваемое на обработку вершин в ближней цепочке, которые затем удаляются на этом же шаге. Поскольку каждая вершина может быть удалена только однажды, стоимость выполнения всех обращений к функции supportingLine в процессе работы алгоритма ограничена сверху величиной О(n).

Оказывается, что функция insertionHull тратит основное время на выполнение функций pointlnConvexPolygon и leastVertex. Для обработки i-той точки s_i обращение к каждой из этих двух функций занимает время, пропорциональное числу i в худшем случае (когда выпуклая оболочка содержит i вершин). Этот случай относится ко всем точкам s_i, если они являются внешними, поскольку текущая оболочка увеличивается на одну вершину при занесении каждой последующей точки. Следовательно, в худшем случае функция insertionHull работает в течение времени O(n²).