2차원에서 선물 포장 알고리즘을 구현하는 C++ 프로그램

우리는 2차원에서 Gift Wrapping Algorithm을 구현하는 C++ 프로그램을 개발할 것입니다. Gift Wrapping Algorithm은 주어진 점 집합의 볼록 껍질을 계산하는 알고리즘입니다.

알고리즘

Begin
   function convexHull() to find convex hull of a set of n points:
   There must be at least three points.
   Initialize the result.
   Find the leftmost point.
   Starting from leftmost point, keep moving counterclockwise
   until reach the start point again.
   Print the result.
End

예시 코드

#include <iostream>
using namespace std;
#define INF 10000
struct P {
   int x;
   int y;
};
int orient(P a, P b, P c) {
   int v = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
   if (v == 0)
      return 0; // colinear
      return (v >0) ? 1 : 2; // clock or counterclock wise
}
void convexHull(P points[], int m) {
   if (m < 3)//at least three points required
      return;
   int n[m];
   for (int i = 0; i < m; i++)
      n[i] = -1;
      int l = 0;//initialize result.
   for (int i = 1; i < m; i++)
      if (points[i].x < points[l].x)
         l = i; //find left most point
         int p = l, q;
   do {
      q = (p + 1) % m;
      for (int i = 0; i < m; i++)
         if (orient(points[p], points[i], points[q]) == 2)
            q = i;
            n[p] = q;
            p = q;
   } while (p != l);
   for (int i = 0; i < m; i++) {
      if (n[i] != -1)
         cout << "(" << points[i].x << ", " << points[i].y << ")\n";
   }
}
int main() {
   P points[] = {{0, 4}, {2, 1}, {2, 3}, {4, 1}, {3, 0}, {1, 1}, {7, 6}};
   cout << "The points in the convex hull are: ";
   int n = sizeof(points) / sizeof(points[0]);
   convexHull(points, n);
   return 0;
}

출력

The points in the convex hull are: (0, 4)
(4, 1)
(3, 0)
(1, 1)
(7, 6)