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

Что такое выпуклая оболочка?

Это наименьший многоугольник, содержащий все точки системы.

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

Алгоритм

Шаг 1.Выберите самые нижние точки (если ничья, выберите крайнюю левую точку). пусть это будет Po(Xo,Yo).

Шаг 2.Отсортируйте точки P по углу между линиями y=Yo и линией, соединяющей точки P и Po. Если угол один и тот же, то расстояние между P и Po будет критерием.

Шаг 3.Удалите точки с общей ориентацией и оставьте самую дальнюю точку. Предположим, что a, b и c имеют одинаковую ориентацию, а точка «c» находится дальше всего от Po, тогда оставьте точку «c» и удалите точки «a» и «b».

Шаг 4.Создайте стек S и поместите в него первые 2 элемента (Po, P1).

Шаг 5.Выберите следующий элемент P из отсортированного списка. Действуйте как следующий псевдокод.

if(vector between top and penultimate point of stack S has 
to move anticlockwise to reach the next element P)
{
 push(P)
}
else
{
  pop()
  push(P)
}

Проблемы

Сравнение ориентации

Это была самая сложная часть реализации.

Мы должны сравнить ориентацию двух точек относительно точки отсчета Po.

пусть есть три точки p,q,r. Мы хотим выяснить, должен ли вектор pq двигаться по часовой стрелке или против часовой стрелки, чтобы достичь точки «r».

Найдем векторное произведение векторов pq и qr

(pq × qr) = |pq||qr|sin(θ), где θ — угол между pq и qr.

Случай 1: точка r направлена ​​против часовой стрелки. Это означает 0‹θ ‹ 180°. Следовательно, sin(θ) ›0. Следовательно, перекрестный продукт будет положительным (+).

Случай 2: точка r направлена ​​по часовой стрелке. Это означает 180°‹θ‹ 360°. Следовательно, sin(θ) ‹0. Следовательно, перекрестный продукт будет положительным (-).

int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
 
    if (val == 0) return 0;  // collinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}

Функция выпуклой оболочки

Следующий код представляет собой код функции выпуклой оболочки.

stack* convexhull(Point pts[],int size) 
{
 // bottom most point(step 1)
 Point bottom=pts[0]; 
 Point temp;
 int min=0;
 for(int i=1;i<size;i++)
 {
  if(pts[i].y<bottom.y)
  {
   bottom=pts[i];
   min=i;
  }

  else if(pts[i].y==bottom.y)
 {
  if(pts[i].x<bottom.x)
  {
   bottom=pts[i];
   min=i;
  }
 }
 }
 p0=bottom; //p0 is the global variable
 temp=pts[0];
 pts[0]=pts[min];
 pts[min]=temp;
// Step 1 ends

//Step 2 starts

 quickSort(pts,0,size-1);

//Step 2 ends

 print_mat(pts,size);

 //step 3 starts

 int m = 1; // Initialize size of modified array
   for (int i=1; i<size; i++)
   {
       // Keep removing i while angle of i and i+1 is same
       // with respect to p0
       while (i < size-1 && orientation(p0, pts[i],pts[i+1]) == 0)
          i++;
       pts[m] = pts[i];
       m++;  // Update size of modified array
   }

   // step 3 ends
//step 4 start

 stack *S=create_node(pts[0]);

 for(int i=1;i<3;i++) 
 {
  push(S,pts[i]);
 }
// step 4 ends
// step 5 start
 for(int i=3;i<size;i++)
 {
  while((siz(S)>1)&&(orientation(get_pen(S)->pt,get_top(S)->pt,pts[i])!=2))
  {
   pop(S);
  } 
   push(S,pts[i]);
 }
// step 5 ends
 return S;
}

Приложения

  1. Обработка изображения. Выпуклую оболочку можно использовать для анализа формы, распознавания объектов и отслеживания объектов. Это помогает упростить представление сложных форм и определить важные особенности изображения.
  2. Распознавание образов. Выпуклые оболочки можно использовать в задачах распознавания образов, таких как распознавание символов, анализ подписи и распознавание лиц, чтобы упростить представление сложных узоров и повысить точность распознавания.
  3. Компьютерная графика. В компьютерной графике выпуклая оболочка используется для обнаружения столкновений, определения видимости и алгоритмов отбраковки, которые оптимизируют производительность рендеринга, исключая ненужные объекты из конвейера рендеринга.
  4. Анализ данных и обнаружение выбросов. При анализе данных выпуклая оболочка может использоваться для выявления выбросов или аномалий. Точки, лежащие за пределами выпуклой оболочки набора данных, могут считаться выбросами или шумом.