пятница, 12 ноября 2010 г.

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

Теория:   Wikipedia, Hardfire

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

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

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

Для начала ознакамливаемся с теоретическим материалом(см. начало поста).

Рассмотрим два подхода к реализации данного алгоритма.
Первый подход: 
Приведу пример функции, реализующую основную логику:

  1. void ConvexHullJarvis(const vector<point> &mas, vector<int> &convex_hull)
  2. {
  3.   // находим самую левую из самых нижних
  4.   int base = 0;
  5.   for (int i=1;i<n;i++)
  6.   {
  7.     if (mas[i].y < mas[base].y)
  8.       base = i;
  9.     else
  10.       if (mas[i].y == mas[base].y &&
  11.         mas[i].x < mas[base].x)
  12.         base = i;
  13.   }
  14.   // эта точка точно входит в выпуклую оболочку
  15.   convex_hull.push_back(base);
  16.  
  17.   point first = mas[base];
  18.   point cur = first;
  19.   point prev = point(first.x - 1, first.y);
  20.   do
  21.   {
  22.     double minCosAngle = 1e9; // чем больше угол, тем меньше его косинус
  23.     double maxLen = 1e9;
  24.     int next = -1;
  25.     for (int i=0;i<n;i++)
  26.     {
  27.       double curCosAngle = CosAngle(prev, cur, mas[i]);
  28.       if (Less(curCosAngle,minCosAngle))
  29.       {
  30.         next = i;
  31.         minCosAngle = curCosAngle;
  32.         maxLen = dist(cur,mas[i]);
  33.       }
  34.       else if (Equal(curCosAngle, minCosAngle))
  35.       {
  36.         double curLen = dist(cur,mas[i]);
  37.         if (More(curLen,maxLen))
  38.         {
  39.           next = i;
  40.           maxLen = curLen;
  41.         }
  42.       }
  43.     }
  44.     prev = cur;
  45.     cur = mas[next];
  46.     convex_hull.push_back(next);
  47.   }
  48.   while (cur != first);
  49. }
* This source code was highlighted with Source Code Highlighter.

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

Как видно из рисунка, на текущем шаге уже найдены три точки, образующие выпуклую оболочку. Это 2, 5 и 8. Следующая точка “i” должна образовывать максимальный угол 5-8-i. Интуитивно понятно, что это будет точка 4.
Сам угол при этом не ищется, а ищется только его косинус. Угол 5-8-i является углом в треугольнике. Значение угла варьируется в интервале [0,180] градусов. Мы помним, что косинус угла в этом интервале является монотонно убывающей функцей. Поэтому можем сделать вывод: чем больше угол, тем меньше его косинус. Этот момент описан в строчках 28-33.
Также не забываем обрабатывать вырожденный случай, когда имеется два претендента(точки A и B) на вакантное место быть следующей точкой в выпуклой оболочке. При этом последняя точка в выпуклой оболочке X и точки A,B лежат на одной прямой. В таком случае нужно выбрать ту точку, которая наиболее удалена от точки X. Этот момент описан в строчках 34-43.
В тот момент, когда следующая точка в выпуклой оболочке совпала с первой, можно сделать вывод, что выпуклая оболочка построена.

Данная реализация имеет ряд минусов. Во первых приходится работать с дробными числами, что влечет за собой написания специальных функций сравнения дробных чисел: Equal, More и Less. Также приходится вычислять расстояние между двумя точками(функция dist), что в свою очередь влечет использование функции взятия квадратного корня. Конечно можно было и не использовать квадратный корень, а считать длины в квадрате. От этого корректность алгоритма не меняется. Но есть способ еще лучше. Его мы рассмотрим во втором подходе.

По
ссылке приведен полный исходный код этого подхода, который является решением задачи 5D. В этой задаче ищется периметр выпуклой оболочки.

Второй подход:
Суть второго подхода описана у команды
HardFire.
Аналог функции, приведенной в первом подходе:

  1. void ConvexHullJarvis(const vector<point> &mas, vector<int> &convex_hull)
  2. {
  3.   // находим самую левую из самых нижних
  4.   int base = 0;
  5.   for (int i=1;i<n;i++)
  6.   {
  7.     if (mas[i].y < mas[base].y)
  8.       base = i;
  9.     else
  10.       if (mas[i].y == mas[base].y &&
  11.         mas[i].x < mas[base].x)
  12.         base = i;
  13.   }
  14.   // эта точка точно входит в выпуклую оболочку
  15.   convex_hull.push_back(base);
  16.  
  17.   int first = base;
  18.   int cur = base;
  19.   do
  20.   {
  21.     int next = (cur + 1) % n;
  22.     for (int i=0;i<n;i++)
  23.     {
  24.       int sign = OrientTriangl2(mas[cur], mas[next], mas[i]);
  25.       // точка mas[i] находится левее прямой ( mas[cur], mas[next] )
  26.       if (sign < 0) // обход выпуклой оболочки против часовой стрелки
  27.         next = i;
  28.       // точка лежит на прямой, образованной точками mas[cur], mas[next]
  29.       else if (sign == 0)
  30.       {
  31.         // точка mas[i] находится дальше, чем mas[next] от точки mas[cur]
  32.         if (isInside(mas[cur],mas[next],mas[i]))
  33.           next = i;
  34.       }
  35.     }
  36.     cur = next;
  37.     convex_hull.push_back(next);
  38.   }
  39.   while (cur != first);
  40. }
* This source code was highlighted with Source Code Highlighter.

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

Полный исходный код лежит:
здесь

3 комментария:

  1. Не указана функция
    convex_hull.push_back
    и непонятно, что она делает

    ОтветитьУдалить
  2. Для начало стоит познакомиться с контейнером vector: http://ru.wikipedia.org/wiki/Vector_(C%2B%2B)

    Далее нужно рассмотреть набор операций, которые реализованы у вектора, в частности метод push_back: http://www.cplusplus.com/reference/vector/vector/push_back/

    И важно не забыть добавить #include в самом начале вашего исходника.

    И только потом стоит возвращаться к данному посту. Успехов!

    ОтветитьУдалить
  3. К сожалению во втором подходе есть недочет. Он на ответ не влияет, если выводить только периметр, но если сделать вывод МВО, то она находится не всегда правильно.
    Например, если подать в программу множество точек: {(1;1),(4;1),(4;3),(1;3),(1;2)}
    То ответ будет: P = 10; МВО = {(1;1),(4;1),(4;3),(1;3),(1;2)} -> т.е. для подсчета P будет делаться 2-ва лишних оборота цикла.
    А МВО должна быть: {(1;1),(4;1),(4;3),(1;3)} и также P будет равно 10.

    На данном примере это не существенно, но Если окажется, что таких точек в конце будет намного больше, то будет сделано очень много лишних операций при подсчете P.

    ОтветитьУдалить