Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // find additional faces
- vector<Polygon> bound_polygon(Polygon &points) {
- reorder_ccw(points);
- rotate(points.begin(), min_element(points.begin(), points.end(), PointCmp()), points.end());
- // find left bottom corner
- const int min_x = min_element(points.begin(), points.end(), PointCmpByX())->x - 1;
- const int min_y = min_element(points.begin(), points.end(), PointCmpByY())->y - 1;
- // find the farthest point
- auto farthest = *max_element(points.begin(), points.end(), [](const Point &a, const Point &b) {
- return a.x + a.y < b.x + b.y;
- });
- // find other coordinates
- const int max_x = farthest.x + (farthest.y - min_y) + 1;
- const int max_y = farthest.y + (farthest.x - min_x) + 1;
- const Polygon triangle = {Point(min_x, min_y, ++max_id),
- Point(max_x, min_y, ++max_id),
- Point(min_x, max_y, ++max_id)};
- int iter = 0;
- Polygon p1;
- p1.push_back(triangle[0]);
- while (points[iter].id != farthest.id) {
- p1.push_back(points[iter++]);
- }
- p1.push_back(points[iter]);
- p1.push_back(triangle[1]);
- Polygon p2;
- p2.push_back(triangle[1]);
- p2.push_back(farthest);
- p2.push_back(triangle[2]);
- Polygon p3;
- p3.push_back(triangle[2]);
- while (iter < points.size()) {
- p3.push_back(points[iter++]);
- }
- p3.push_back(points[0]);
- p3.push_back(triangle[0]);
- vector<Polygon> faces = {p1, p2, p3};
- return faces;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement