Университет города Переславля

      "Алгоритмы непрерывной математики"
    осенний семестр 1998-99 учебного года
               С.В.Дужин

                Лекция 5
    Алгоритм построения выпуклой оболочки на плоскости

Определение 1.
Множество S  в n-мерном пространстве R^n называется выпуклым, если
вместе с каждой парой своих точек оно содержит весь отрезок, их
соединяющий.

Примеры: выпуклый многоугольник, невыпуклый многоугольник, эллипс
с внутренностью.

Координаты любой точки отрезка PQ можно записать в виде uP+vQ,
где u>=0, v>=0, u+v=1.

Определение 2.
Выпуклая комбинация точек P_1, ..., P_k n-мерного пространства -- 
это точка
    a_1P_1 + ... + a_kP_k,
где a_i -- неотрицательные  действительные числа, сумма которых равна 1,
а операции сложения и умножения на число выполняются покомпонентно.

Примеры:
  выпуклая оболочка двух точек P и Q -- это отрезок [PQ].
  выпуклая оболочка трех точек P, Q, R, не лежащих на одной прямой, -- 
это треугольник [PQR] (с внутренностью).
  выпуклая оболочка четырех точек пространства, не лежащих в одной
плоскости -- это тетраэдр (с внутренностью).
  выпуклая оболочка четырех точек, лежащих в одной плоскости, может
быть треугольником или четырехугольником, в зависимости от взаимного
расположения этих точек.

Определение 3.
Множество всех выпуклых комбинаций точек данного множества L называется
его выпуклой оболочкой:
   conv(L) = { a_1P_1 + ... + a_kP_k | P_i \in L, a_i>=0, a_1+...+a_k=1 }.

Утверждение. Выпуклая оболочка L -- это наименьшее выпуклое множество,
содержащее L.

Теорема 1. Выпуклая оболочка множества в R^n состоит из выпуклых 
комбинаций всех наборов из не более чем (n+1) точки этого множества
(т.е. в определении 3 можно ограничиться значениями k <= n+1).

Например, на плоскости выпуклая оболочка конечного можества L равна
объединению всех треугольников, вершины которых принадлежат L.

Определение 4. Точка выпуклого множества S называется крайней: если
она не является внутренней точкой никакого отрезка с концами,
принадлежащими S.

Примеры.
  Крайние точки выпуклого многоугольника на плоскости -- это его
вершины. Крайние точки эллипса с внутренностью -- это точки граничной
кривой.

Теорема 2. Если E -- множество крайних точек выпуклого множества S,
то conv(E)=S. При этом E является наименьшим множеством, которое
обладает этим свойством (для данного S).

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

Задача.
Дано конечное множество точек плоскости P={P_1,...,P_N}.
Требуется описать его выпуклую оболочку, т.е.:
   1. Из множества P выделить множество крайних точек K.
   2. Крайние точки упорядочить в том порядке, в котором они встречаются
при обходе границы многоугольника conv(P) против часовой стрелки.

Наивный алгоритм построения выпуклой оболочки.
   1. Перебираем все пары, состоящие из точки P_n и треугольника
P_i,P_j,P_k. Если данная точка оказалась внутри треугольника,
удаляем ее из списка P. Остается список крайних точек.
   2. Выбрав некоторую внутреннюю точку Q выпуклой оболочки,
упорядочиваем список крайних точек в порядке возрастания полярного угла,
который отсчитывается от точки Q.

Задание на дом.
Составить и отладить программу на C, реализующую этот алгоритм.
Программа должна читать данные из stdin и выдавать результат на stdout.
Формат входного файла: в первой строке число N, в остальных N строках
-- координаты очередной точки через пробел.
Выходной файл должен содержать список вершин выпуклого многоугольника
в таком же формате.
Программы выслать до 12.10.98 по адресу duzhin@botik.ru.

Литература.
Препарата, Шеймос. Вычислительная геометрия. Введение.
(есть в библиотеке ИПС).