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

Алгоритм Джарвіса (або алгоритм загортання подарунка) — алгоритм знаходження опуклої оболонки. Часова складність — О(n * h), де n — кількість точок, h — кількість точок опуклої оболонки. Тобто, алгоритм найбільш ефективний у випадку малої кількості точок опуклої оболонки.

Опис алгоритму

Нехай шукана опукла оболонка множини ${\displaystyle P=\{p_{1},p_{2},...p_{n}\}}$ точок. Як початкову беремо найлівішу точку (точку з найменшою x-координатою), якщо їх буде декілька, то виберемо серед них найнижчу (точку з найменшою y-координатою). Нехай знайдена точка — точка ${\displaystyle p_{1}}$ (її можна знайти за час ${\displaystyle O(n)}$ звичайним проходом по всіх точках і порівнянням координат). Точка ${\displaystyle p_{1}}$ напевно є вершиною опуклої оболонки. Далі для кожної точки ${\displaystyle p_{i}}$ шукаємо проти годинникової стрілки точки ${\displaystyle p_{i+1}}$ шляхом знаходження за ${\displaystyle O(n)}$ серед точок, що залишились, (включно з ${\displaystyle p_{1}}$) точку з найменшим полярним кутом ${\displaystyle p_{i-1}p_{i}p_{i+1}}$. Вона і буде наступною вершиною опуклої оболонки. При цьому не обов'язково обчислювати кут — достатньо обчислити векторний добуток (узагальненням векторного добутку для двовимірного випадку є ) між векторами ${\displaystyle p_{i}p'_{i+1}}$ та ${\displaystyle p_{i}p''_{i+1}}$, де ${\displaystyle p'_{i+1}}$ — знайдений на даний момент мінімум, ${\displaystyle p''_{i+1}}$ — претендент (першим мінімумом може бути обрана довільна точка). Якщо векторний добуток від'ємний, то знайдено новий мінімум. Якщо рівний нулю, тобто ${\displaystyle p'_{i+1}}$ та ${\displaystyle p''_{i+1}}$ лежать на одній прямій, то мінімум — та, яка лежить далі від точки ${\displaystyle p_{i}}$. Алгоритм продовжує роботу доки ${\displaystyle p_{i+1}\neq p_{1}}$. Чому алгоритм зупиниться? Тому, що точка ${\displaystyle p_{1}}$ (найнижча серед найлівіших точок) у будь-якому випадку належить до точок опуклої оболонки.

Псевдокод

Jarvis(P) 1) p[1] = найнижча серед найлівіших точок множини P; 2) i = 1; 3) do: p[i+1] = довільна точка з P (крім вже зарахованих до опуклої оболонки, але включно з p[1]); (a)for (для кожної точки j з P, крім вже зарахованих до опуклої оболонки, але включно з p[1] p[i+1] = min_polar_angle(p[i+1], P[j]); // мінімум через векторний добуток (b)i = i + 1; while p[i] != p[1] 4) return p; 

Реалізація на С++

  //Point - some type that has x, y members and //for which operator != is defined template <typename Point> inline bool determinantSignum(const Point& a,  const Point& b,  const Point& c) {  return (((b.x - a.x) * (c.y - b.y) -  (c.x - b.x) * (b.y - a.y)) >= 0); } template <typename Point> void jarvis(const std::vector<Point> & source,  std::vector<Point>& result) {  if (source.empty())  {  return;  }  std::vector<Point> src = source;  typedef typename std::vector<Point>::iterator PointIterator;  PointIterator leftDownIt = src.begin();  PointIterator it = leftDownIt + 1;  Point currentPoint;  Point leftDownPoint = *(leftDownIt);  // Finding leftest lowest point  for (PointIterator end = src.end(); it != end; ++it)  {  currentPoint = *it;  if (currentPoint.x < leftDownPoint.x)  {  leftDownPoint = currentPoint;  leftDownIt = it;  }  else if (currentPoint.x == leftDownPoint.x  && currentPoint.y < leftDownPoint.y)  {  leftDownPoint = currentPoint;  leftDownIt = it;  }  }  // Add selected point to answer  src.erase(leftDownIt);  result.push_back(leftDownPoint);  currentPoint = leftDownPoint;  Point nextPoint, tryPoint;  PointIterator nextIt;  do  {  nextPoint = leftDownPoint;  nextIt = it;  it = src.begin();  for (PointIterator end = src.end(); it != end; ++it)  {  tryPoint = *it;  if (determinantSignum(nextPoint,  currentPoint,  tryPoint))  {  nextPoint = tryPoint;  nextIt = it;  }  }  if (nextPoint != leftDownPoint)  {  src.erase(nextIt);  result.push_back(nextPoint);  currentPoint = nextPoint;  }  }  while (nextPoint != leftDownPoint); } 

Див. також

• Алгоритм Грехема
• Алгоритм Чана

Посилання

• Реалізація на С++. Містить помилку в обрахунку векторного добутку. Виправлено у наведеному вище коді. [ 6 липня 2012 у Wayback Machine.]

Література

• Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. — М. : Мир, 1989. — 478 с. — .
• Jarvis, R. A. (1973). On the identification of the convex hull of a finite set of points in the plane. . 2: 18—21. doi:10.1016/0020-0190(73)90020-3.