将凸包多边形a优化为外接四边形b

admin1

要将凸包多边形a优化为外接四边形b，需要找到a的四个顶点，也就是距离凸包中心最远的点。具体实现可以采用旋转卡壳算法，该算法的主要思想是在凸包上选择一条边，然后将其与凸包上的其它边依次进行配对，以此得到凸包上任意两个点间的距离，并找到距离最大的两个点。这样就可以得到一个外接矩形，其四个顶点就是凸包中距离最远的四个点。

1. #include <iostream>
2. #include <algorithm>
3. #include <cmath>
4. using namespace std;
6. struct Point{
7.     double x, y;
8. };
10. double cross(Point a, Point b, Point c){
11.     return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
12. }
14. double dist(Point a, Point b){
15.     return sqrt((b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y));
16. }
18. void rotating采用calipers(Point p[], int n, Point res[]){
19.     int j = 1, k = 1;
20.     for(int i=0; i<n; i++){
21.         while(cross(p[i], p[(i+1)%n], p[j]) > cross(p[i], p[(i+1)%n], p[(j+1)%n])){
22.             j = (j+1)%n;
23.         }
24.         while(dist(p[i], p[k]) < dist(p[i], p[(k+1)%n])){
25.             k = (k+1)%n;
26.         }
27.         if(i==0) res = p[i];
28.         if(i==n-1) res = p[i];
29.         if(dist(p[i], p[j]) > dist(res, res)){
30.             res = p[i];
31.             res = p[j];
32.         }
33.         if(cross(p[(i+1)%n], p[i], p[k]) > cross(p[(i+1)%n], p[i], p[(k+1)%n])){
34.             while(cross(p[(i+1)%n], p[i], p[k]) > cross(p[(i+1)%n], p[i], p[(k+1)%n])){
35.                 k = (k+1)%n;
36.             }
37.             if(dist(p[i], p[k]) > dist(res, res)){
38.                 res = p[k];
39.             }
40.             if(dist(p[j], p[(k+1)%n]) > dist(res, res)){
41.                 res = p[(k+1)%n];
42.             }
43.         }
44.         else{
45.             while(cross(p[(i+1)%n], p[i], p[j]) < cross(p[(i+1)%n], p[i], p[(j+1)%n])){
46.                 j = (j+1)%n;
47.             }
48.             if(dist(p[j], p[i]) > dist(res, res)){
49.                 res = p[j];
50.             }
51.             if(dist(p[k], p[(j+1)%n]) > dist(res, res)){
52.                 res = p[(j+1)%n];
53.             }
54.         }
55.     }
56. }
58. int main(){
59.     int n;
60.     cin >> n;
61.     Point* p = new Point[n];
62.     for(int i=0; i<n; i++){
63.         cin >> p[i].x >> p[i].y;
64.     }
65.     sort(p, p+n, [](Point a, Point b){
66.         return a.x < b.x || (a.x==b.x && a.y < b.y);
67.     });
68.     Point* res = new Point;
69.     rotating采用calipers(p, n, res);
70.     cout << "The four vertices of the optimized rectangle are: " << endl;
71.     for(int i=0; i<4; i++){
72.         cout << "(" << res[i].x << ", " << res[i].y << ")" << endl;
73.     }
74.     delete[] p;
75.     delete[] res;
76.     return 0;
77. }

复制代码