分治算法求解凸包问题

admin

1. #include <iostream>
   
2. #include <vector>
   
3. #include <cmath>
   
4. #include <algorithm>
   
5. 
   
6. using namespace std;
   
7. 
   
8. // 定义点的结构体
   
9. struct Point {
   
10.     int x, y;
    
11. };
    
12. 
    
13. // 计算点P到直线AB的距离
    
14. double distanceToLine(const Point& A, const Point& B, const Point& P) {
    
15.     return abs((B.x - A.x) * (A.y - P.y) - (A.x - P.x) * (B.y - A.y)) /
    
16.         sqrt(pow(B.x - A.x, 2) + pow(B.y - A.y, 2));
    
17. }
    
18. 
    
19. // 计算叉积，判断点C在向量AB的右侧、左侧或共线
    
20. int crossProduct(const Point& A, const Point& B, const Point& C) {
    
21.     return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
    
22. }
    
23. 
    
24. // 判断点C是否在向量AB的右侧
    
25. bool isRightOf(const Point& A, const Point& B, const Point& C) {
    
26.     return crossProduct(A, B, C) < 0;
    
27. }
    
28. 
    
29. // 快速凸包算法的部分实现
    
30. vector<Point> quick_half_hull(vector<Point>& S, const Point& a, const Point& b) {
    
31.     if (S.empty()) return {};
    
32. 
    
33.     double maxDist = -1;
    
34.     Point c;
    
35.     for (const auto& point : S) {
    
36.         double dist = distanceToLine(a, b, point);
    
37.         if (dist > maxDist) {
    
38.             maxDist = dist;
    
39.             c = point;
    
40.         }
    
41.     }
    
42. 
    
43.     vector<Point> A, B;
    
44. 
    
45.     // 筛选出右侧的点集A和B
    
46.     for (const auto& point : S) {
    
47.         if (isRightOf(b, c, point)) {
    
48.             A.push_back(point);
    
49.         }
    
50.         else if (isRightOf(c, a, point)) {
    
51.             B.push_back(point);
    
52.         }
    
53.     }
    
54. 
    
55.     vector<Point> QA = quick_half_hull(A, a, c);
    
56.     vector<Point> QB = quick_half_hull(B, c, b);
    
57. 
    
58.     vector<Point> result;
    
59.     result.insert(result.end(), QA.begin(), QA.end());
    
60.     result.push_back(c);
    
61.     result.insert(result.end(), QB.begin(), QB.end());
    
62. 
    
63.     return result;
    
64. }
    
65. 
    
66. vector<Point> quick_hull(vector<Point>& S) {
    
67.     if (S.size() < 3) return S;
    
68. 
    
69.     // 寻找极端点a和b
    
70.     sort(S.begin(), S.end(), [](const Point& p1, const Point& p2) {
    
71.         return (p1.x < p2.x) || (p1.x == p2.x && p1.y < p2.y);
    
72.         });
    
73. 
    
74.     Point a = S[0];
    
75.     Point b = S[S.size() - 1];
    
76. 
    
77.     vector<Point> A, B;
    
78. 
    
79.     // 筛选出右侧的点集A和B
    
80.     for (const auto& point : S) {
    
81.         if (isRightOf(b, a, point)) {
    
82.             A.push_back(point);
    
83.         }
    
84.         else if (isRightOf(a, b, point)) {
    
85.             B.push_back(point);
    
86.         }
    
87.     }
    
88. 
    
89.     vector<Point> QA = quick_half_hull(A, a, b);
    
90.     vector<Point> QB = quick_half_hull(B, b, a);
    
91. 
    
92.     vector<Point> result;
    
93.     result.push_back(a);
    
94.     result.insert(result.end(), QA.begin(), QA.end());
    
95.     result.push_back(b);
    
96.     result.insert(result.end(), QB.begin(), QB.end());
    
97. 
    
98.     return result;
    
99. }
    
100. 
     
101. int main() {
     
102.     // 示例点集
     
103.     vector<Point> points = { {0, 0}, {4, 4}, {4, 0}, {0, 4}, {3, 3} ,{3,1},{2,1},{1,2},{3,2},{4,3},{2,4} ,{0,2},{0,5} };
     
104. 
     
105.     // 调用凸包算法
     
106.     vector<Point> result = quick_hull(points);
     
107. 
     
108.     // 输出凸包顶点
     
109.     cout << "Convex Hull Points:\n";
     
110.     for (const auto& point : result) {
     
111.         cout << "(" << point.x << ", " << point.y << ")\n";
     
112.     }
     
113. 
     
114.     return 0;
     
115. }
     

复制代码