Advertisement
Guest User

Untitled

a guest
Dec 18th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. // find additional faces
  2. vector<Polygon> bound_polygon(Polygon &points) {
  3.     reorder_ccw(points);
  4.     rotate(points.begin(), min_element(points.begin(), points.end(), PointCmp()), points.end());
  5.  
  6.     // find left bottom corner
  7.     const int min_x = min_element(points.begin(), points.end(), PointCmpByX())->x - 1;
  8.     const int min_y = min_element(points.begin(), points.end(), PointCmpByY())->y - 1;
  9.  
  10.     // find the farthest point
  11.     auto farthest = *max_element(points.begin(), points.end(), [](const Point &a, const Point &b) {
  12.         return a.x + a.y < b.x + b.y;
  13.     });
  14.  
  15.     // find other coordinates
  16.     const int max_x = farthest.x + (farthest.y - min_y) + 1;
  17.     const int max_y = farthest.y + (farthest.x - min_x) + 1;
  18.  
  19.     const Polygon triangle = {Point(min_x, min_y, ++max_id),
  20.                               Point(max_x, min_y, ++max_id),
  21.                               Point(min_x, max_y, ++max_id)};
  22.  
  23.     int iter = 0;
  24.  
  25.     Polygon p1;
  26.     p1.push_back(triangle[0]);
  27.     while (points[iter].id != farthest.id) {
  28.         p1.push_back(points[iter++]);
  29.     }
  30.     p1.push_back(points[iter]);
  31.     p1.push_back(triangle[1]);
  32.  
  33.     Polygon p2;
  34.     p2.push_back(triangle[1]);
  35.     p2.push_back(farthest);
  36.     p2.push_back(triangle[2]);
  37.  
  38.     Polygon p3;
  39.     p3.push_back(triangle[2]);
  40.     while (iter < points.size()) {
  41.         p3.push_back(points[iter++]);
  42.     }
  43.     p3.push_back(points[0]);
  44.     p3.push_back(triangle[0]);
  45.  
  46.     vector<Polygon> faces = {p1, p2, p3};
  47.  
  48.     return faces;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement