分治算法求解凸包问题

admin

1. #include <iostream>
2. #include <vector>
3. #include <cmath>
4. #include <algorithm>
6. using namespace std;
8. // 定义点的结构体
9. struct Point {
10.     int x, y;
11. };
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. }
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. }
24. // 判断点C是否在向量AB的右侧
25. bool isRightOf(const Point& A, const Point& B, const Point& C) {
26.     return crossProduct(A, B, C) < 0;
27. }
29. // 快速凸包算法的部分实现
30. vector<Point> quick_half_hull(vector<Point>& S, const Point& a, const Point& b) {
31.     if (S.empty()) return {};
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.     }
43.     vector<Point> A, B;
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.     }
55.     vector<Point> QA = quick_half_hull(A, a, c);
56.     vector<Point> QB = quick_half_hull(B, c, b);
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());
63.     return result;
64. }
66. vector<Point> quick_hull(vector<Point>& S) {
67.     if (S.size() < 3) return S;
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.         });
74.     Point a = S[0];
75.     Point b = S[S.size() - 1];
77.     vector<Point> A, B;
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.     }
89.     vector<Point> QA = quick_half_hull(A, a, b);
90.     vector<Point> QB = quick_half_hull(B, b, a);
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());
98.     return result;
99. }
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} };
105.     // 调用凸包算法
106.     vector<Point> result = quick_hull(points);
108.     // 输出凸包顶点
109.     cout << "Convex Hull Points:\n";
110.     for (const auto& point : result) {
111.         cout << "(" << point.x << ", " << point.y << ")\n";
112.     }
114.     return 0;
115. }

复制代码