Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 볼록 헐 모노톤 체인 알고리즘

<시간/>

이 튜토리얼에서는 주어진 점 집합의 볼록 껍질을 찾는 프로그램에 대해 논의할 것입니다.

볼록 껍질은 그림 내부의 경계에 있는 모든 주어진 점을 포함하는 가장 작은 다각형 볼록 그림입니다.

예시

#include <bits/stdc++.h>
#define llu long long int
using namespace std;
//structure for the given point
struct Point {
   llu x, y;
   bool operator<(Point p){
   return x < p.x || (x == p.x && y < p.y);
   }
};
//calculating the cross product of self made vectors
llu calc_crossproduct(Point O, Point A, Point B){
   return (A.x - O.x) * (B.y - O.y)
   - (A.y - O.y) * (B.x - O.x);
}
//calculating the points on boundary
vector<Point> convex_hull(vector<Point> A){
   int n = A.size(), k = 0;
   if (n <= 3)
   return A;
   vector<Point> ans(2 * n);
   //sorting points lexicographically
   sort(A.begin(), A.end());
   for (int i = 0; i < n; ++i) {
      while (k >= 2 && calc_crossproduct(ans[k - 2],
      ans[k - 1], A[i]) <= 0)
      k--;
      ans[k++] = A[i];
   }
   //building upper hull
   for (size_t i = n - 1, t = k + 1; i > 0; --i) {
      while (k >= t && calc_crossproduct(ans[k - 2],
      ans[k - 1], A[i - 1]) <= 0)
      k--;
      ans[k++] = A[i - 1];
   }
   //resizing the given array
   ans.resize(k - 1);
   return ans;
}
int main(){
   vector<Point> points;
   points.push_back({ 0, 3 });
   points.push_back({ 2, 2 });
   points.push_back({ 1, 1 });
   points.push_back({ 2, 1 });
   points.push_back({ 3, 0 });
   points.push_back({ 0, 0 });
   points.push_back({ 3, 3 });
   vector<Point> ans = convex_hull(points);
   for (int i = 0; i < ans.size(); i++)
   cout << "(" << ans[i].x << ", "
   << ans[i].y << ")" << endl;
   return 0;
}

출력

(0, 0)
(3, 0)
(3, 3)
(0, 3)