C-10 凸包

凸包

数学定义

• 平面的一个子集S被称为是凸的，当且仅当对于任意两点A，B属于S，线段PS都完全属于S
• 过于基础就不详细介绍了
  

凸包的计算

• github上找到了别人的代码，用4种方式实现了凸包的计算，把他放在这里
• 链接地址https://github.com/MiguelVieira/ConvexHull2D
• 先放这个代码的用法吧

int main() {
	vector<point> v = getPoints();
//1
	vector<point> h = quickHull(v);
	cout << "quickHull point count: " << h.size() << endl;
	print(h);
    
//2
	h = giftWrapping(v);
	cout << endl << "giftWrapping point count: " << h.size() << endl;
	print(h);
    
//3
	h = monotoneChain(v);
	cout << endl << "monotoneChain point count: " << h.size() << endl;
	print(h);
    
//4
	h = GrahamScan(v);
	cout << endl << "GrahamScan point count: " << h.size() << endl;
	print(h);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 这是具体的代码，直接写在一个头文件里，包含一下就能在程序里实现上面的诸多用法了

#include <algorithm>
#include <iostream>
#include <vector>
#include<random>
	using namespace std;
namespace ch{
	struct point {
		float x;
		float y;

		point(float xIn, float yIn) : x(xIn), y(yIn) { }
	};

	// The z-value of the cross product of segments 
	// (a, b) and (a, c). Positive means c is ccw
	// from (a, b), negative cw. Zero means its collinear.
	float ccw(const point& a, const point& b, const point& c) {
		return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
	}

	// Returns true if a is lexicographically before b.
	bool isLeftOf(const point& a, const point& b) {
		return (a.x < b.x || (a.x == b.x && a.y < b.y));
	}

	// Used to sort points in ccw order about a pivot.
	struct ccwSorter {
		const point& pivot;

		ccwSorter(const point& inPivot) : pivot(inPivot) { }

		bool operator()(const point& a, const point& b) {
			return ccw(pivot, a, b) < 0;
		}
	};

	// The length of segment (a, b).
	float len(const point& a, const point& b) {
		return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
	}

	// The unsigned distance of p from segment (a, b).
	float dist(const point& a, const point& b, const point& p) {
		return fabs((b.x - a.x) * (a.y - p.y) - (b.y - a.y) * (a.x - p.x)) / len(a, b);
	}

	// Returns the index of the farthest point from segment (a, b).
	size_t getFarthest(const point& a, const point& b, const vector<point>& v) {
		size_t idxMax = 0;
		float distMax = dist(a, b, v[idxMax]);

		for (size_t i = 1; i < v.size(); ++i) {
			float distCurr = dist(a, b, v[i]);
			if (distCurr > distMax) {
				idxMax = i;
				distMax = distCurr;
			}
		}

		return idxMax;
	}


	// The gift-wrapping algorithm for convex hull.
	// https://en.wikipedia.org/wiki/Gift_wrapping_algorithm
	vector<point> giftWrapping(vector<point> v) {
		// Move the leftmost point to the beginning of our vector.
		// It will be the first point in our convext hull.
		swap(v[0], *min_element(v.begin(), v.end(), isLeftOf));

		vector<point> hull;
		// Repeatedly find the first ccw point from our last hull point
		// and put it at the front of our array. 
		// Stop when we see our first point again.
		do {
			hull.push_back(v[0]);
			swap(v[0], *min_element(v.begin() + 1, v.end(), ccwSorter(v[0])));
		} while (v[0].x != hull[0].x && v[0].y != hull[0].y);

		return hull;
	}


	// The Graham scan algorithm for convex hull.
	// https://en.wikipedia.org/wiki/Graham_scan
	vector<point> GrahamScan(vector<point> v) {
		// Put our leftmost point at index 0
		swap(v[0], *min_element(v.begin(), v.end(), isLeftOf));

		// Sort the rest of the points in counter-clockwise order
		// from our leftmost point.
		sort(v.begin() + 1, v.end(), ccwSorter(v[0]));

		// Add our first three points to the hull.
		vector<point> hull;
		auto it = v.begin();
		hull.push_back(*it++);
		hull.push_back(*it++);
		hull.push_back(*it++);

		while (it != v.end()) {
			// Pop off any points that make a convex angle with *it
			while (ccw(*(hull.rbegin() + 1), *(hull.rbegin()), *it) >= 0) {
				hull.pop_back();
			}
			hull.push_back(*it++);
		}

		return hull;
	}


	// The monotone chain algorithm for convex hull.
	vector<point> monotoneChain(vector<point> v) {
		// Sort our points in lexicographic order.
		sort(v.begin(), v.end(), isLeftOf);

		// Find the lower half of the convex hull.
		vector<point> lower;
		for (auto it = v.begin(); it != v.end(); ++it) {
			// Pop off any points that make a convex angle with *it
			while (lower.size() >= 2 && ccw(*(lower.rbegin() + 1), *(lower.rbegin()), *it) >= 0) {
				lower.pop_back();
			}
			lower.push_back(*it);
		}

		// Find the upper half of the convex hull.
		vector<point> upper;
		for (auto it = v.rbegin(); it != v.rend(); ++it) {
			// Pop off any points that make a convex angle with *it
			while (upper.size() >= 2 && ccw(*(upper.rbegin() + 1), *(upper.rbegin()), *it) >= 0) {
				upper.pop_back();
			}
			upper.push_back(*it);
		}

		vector<point> hull;
		hull.insert(hull.end(), lower.begin(), lower.end());
		// Both hulls include both endpoints, so leave them out when we 
		// append the upper hull.
		hull.insert(hull.end(), upper.begin() + 1, upper.end() - 1);
		return hull;
	}


	// Recursive call of the quickhull algorithm.
	void quickHull(const vector<point>& v, const point& a, const point& b,
		vector<point>& hull) {
		if (v.empty()) {
			return;
		}

		point f = v[getFarthest(a, b, v)];

		// Collect points to the left of segment (a, f)
		vector<point> left;
		for (auto p : v) {
			if (ccw(a, f, p) > 0) {
				left.push_back(p);
			}
		}
		quickHull(left, a, f, hull);

		// Add f to the hull
		hull.push_back(f);

		// Collect points to the left of segment (f, b)
		vector<point> right;
		for (auto p : v) {
			if (ccw(f, b, p) > 0) {
				right.push_back(p);
			}
		}
		quickHull(right, f, b, hull);
	}

	// QuickHull algorithm. 
	// https://en.wikipedia.org/wiki/QuickHull
	vector<point> quickHull(const vector<point>& v) {
		vector<point> hull;

		// Start with the leftmost and rightmost points.
		point a = *min_element(v.begin(), v.end(), isLeftOf);
		point b = *max_element(v.begin(), v.end(), isLeftOf);

		// Split the points on either side of segment (a, b)
		vector<point> left, right;
		for (auto p : v) {
			ccw(a, b, p) > 0 ? left.push_back(p) : right.push_back(p);
		}

		// Be careful to add points to the hull
		// in the correct order. Add our leftmost point.
		hull.push_back(a);

		// Add hull points from the left (top)
		quickHull(left, a, b, hull);

		// Add our rightmost point
		hull.push_back(b);

		// Add hull points from the right (bottom)
		quickHull(right, b, a, hull);

		return hull;
	}

	vector<point> getPoints() {
		vector<point> v;
		std::default_random_engine e(std::random_device{}());
		std::uniform_real_distribution<double> dist_x(0.05, 0.95);
		std::uniform_real_distribution<double> dist_y(0.05, 0.95);


		for (int i = 0; i < 30; ++i) {
			v.push_back(point(dist_x(e), dist_y(e)));
		}

		return v;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

可视化实现

这个exe小程序我放在主页了，大家可以免费下载，之后会创建一个仓库把代码公开出来，大家就可以在我的基础上实现更多的几何算法。