:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Выпуклая оболочка » Алгоритм Мелькмана
На правах рекламы
http://prostodveri.com.ua/mezhkomnatnye-dveri межкомнатные двери, купить межкомнатные.
  Алгоритм Мелькмана



Перевод: Кантор И.
e-mail: algolist@mail.ru
web: iliakan@gmail.com

     Этот алгоритм за O( n ) времени 'выправляет' впуклости многоугольника, то есть замкнутой непересекающейся ломаной, строя таким образом выпуклую оболочку.

     Что интересно, точки могут поступать по мере выполнения алгоритма, и их количество может быть заранее не известно. Главное, чтобы ломаная не пересекалась.

     Для начала объявим вспомогательную функцию, которая для любой тройки x, y, z будет f>0, f=0 или f<0 в зависимости от того, находится ли z справа, на одной линии или слева от линии (x, y).



     Пусть ломаная задана точками v1, ..., vm.

     Алгоритм начинает с пустого дека D.
Дек - список с операциями:
push v - положить элемент на верх дека,
insert v - положить элемент под низ дека,
pop - убрать верхний элемент дека,
remove - удалить нижний элемент дека.





  Псевдокод.



Шаг 1:
          Ввод v1, v2, v3;
          if (v1,v2,v3)>0
            then {push v1; push v2;}
              else {push v2; push v1;}
          push v3; insert v3;

Шаг 2:

          Ввод v;
          until ((v,db,db+1)<0 or (dt-1,dt,c)<0) do { ввод v }; 

Шаг 3:

          until ((dt-1,dt,v)>0) do pop;
          push v;

Шаг 4:

          until ((v,db,db+1)>0) do remove;
          insert v;
          Идти на Шаг 2.