凸包算法详解（convex hull）
一.概念
凸包是一个计算几何（图形学）中的概念。
在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集被称为X的凸包。
X的凸包可以用X内所有点（X1…Xn）的线性组合来构造。
在二维欧几里得空间中，凸包可想象为一条刚好包着所有点得橡皮圈。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。
例子：假设平面上有p0-p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包起来”，当这个多边形是凸多边形的时候，我们就叫它“凸包”。
二.解法
Graham扫描法
时间复杂度：O(nlogn)
思路：Graham扫描的思想就是先找到凸包上的一个点，然后从那个点开始按逆时针方向逐个找凸包上的点，实际上就是进行极角排序，然后对其进行查询使用。
步骤：1. 把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，例如p0
2. 把所有点的坐标平移一下， 使P0作为原点
3. 计算各个点相对于P0的幅角α，按从小到大的顺序对各个点排序。当α相同时，距离p0比较近的排在前面。结果中的第一个点和最后一个点一定是凸包上的点。
以上我们知道了凸包上的第一个点p0和第二个点p1，我们把它们放在栈里面。现在从步骤3那里求得的那个结果里，把p1后面的那个点拿出来做当前点，即p2.接下来开始找第三个点：
- 连接P0和栈顶那个点，得到直线L。看当前点是在直线L的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。
- 如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。
- 当前点是凸包上的点，把它压入栈，执行步骤7。
- 检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把P2后面那个点做当前点，返回步骤4。
CPP代码：
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
| #include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
int i, size = 4;
double px, py;
cout << "please input the size";
cin >> size;
mpoint *points;
int miny_point_id;
double *mcos;
points = new mpoint[size];
mcos = new double[size];
for(i 0; i < size; i++)
{
cin >> px;
cin >> py;
points[i].x = px;
points[i].y = py;
}
class mpoint{ //class point(x, y)
public:
double x;
double y;
mpoint(double xx = 0, double yy = 0){
x = xx;
y = yy;
}
};
int get_miny_point_id(mpoint *points, int size){ //get the point with min_y
int i, min_id = 0;
double miny = 10000;
for(i = 0; i < size; i++){
if(points[i].y < miny){
miny = points[i].y;
min_id = i;
}
}
return min_id;
}
void get_cos(mpoint *points, double *mcos, int id, int size){ //get point's cos
int i;
double coss;
for(i = 0; i < size; i++){
if(i == id){
mcos[i] = 2;
}
else{
coss = (points[i].x - points[id].x) / sqrt((points[i].x - points[id].x) * (points[i].x - points[id].x) + (points[i].y - points[id].y) * (points[i].y - points[id].y));
mcos[i] = coss;
}
}
}
void sort_points(mpoint *points, double *mcos, int size){ //sort the points
int i, j;
double temp_cos;
mpoint temp_point;
for(i = 0; i < size; i++){
for(j = 0; j < size - i - 1; j++){ //bubble sorting
if(mcos[j] < mcos[j + 1]){
temp_cos = mcos[j];
mcos[j] = mcos[j + 1];
mcos[j + 1] = temp_cos;
temp_point = points[j];
points[j] = points[j + 1];
points[j + 1] = temp_point;
}
}
}
}
int ccw(mpoint a, mpoint b, mpoint c){ //judge if it is couter-colockwise
double area2 = (b.x-a.x) * (c.y-a.y) - (b.y-a.y) * (c.x-a.x);
if (area2 < 0){
return -1; // clockwise
}
else{
if (area2 > 0) return 1; // counter-clockwise
else return 0; // collinear
}
}
void get_outpoint(mpoint *points, int size){ //get points in stack
int i, k;
vector <mpoint>outpoint;
outpoint.push_back(points[0]);
outpoint.push_back(points[1]);
i = 2;
while(true){
if(i == size){
break;
}
if(ccw(outpoint[outpoint.size() - 2], outpoint[outpoint.size() - 1], points[i]) > 0){
outpoint.push_back(points[i]);
i = i + 1;
}
else{
outpoint.pop_back();
}
}
cout << "The outpoints are: " << endl;
for(k = 0; k < outpoint.size(); k++){
cout << outpoint[k].x << " " << outpoint[k].y << endl;
}
}
}
|
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
| class mpoint{ //class point(x, y)
public:
double x;
double y;
mpoint(double xx = 0, double yy = 0){
x = xx;
y = yy;
}
};
int get_miny_point_id(mpoint *points, int size){ //get the point with min_y
int i, min_id = 0;
double miny = 10000;
for(i = 0; i < size; i++){
if(points[i].y < miny){
miny = points[i].y;
min_id = i;
}
}
return min_id;
}
void get_cos(mpoint *points, double *mcos, int id, int size){ //get point's cos
int i;
double coss;
for(i = 0; i < size; i++){
if(i == id){
mcos[i] = 2;
}
else{
coss = (points[i].x - points[id].x) / sqrt((points[i].x - points[id].x) * (points[i].x - points[id].x) + (points[i].y - points[id].y) * (points[i].y - points[id].y));
mcos[i] = coss;
}
}
}
void sort_points(mpoint *points, double *mcos, int size){ //sort the points
int i, j;
double temp_cos;
mpoint temp_point;
for(i = 0; i < size; i++){
for(j = 0; j < size - i - 1; j++){ //bubble sorting
if(mcos[j] < mcos[j + 1]){
temp_cos = mcos[j];
mcos[j] = mcos[j + 1];
mcos[j + 1] = temp_cos;
temp_point = points[j];
points[j] = points[j + 1];
points[j + 1] = temp_point;
}
}
}
}
int ccw(mpoint a, mpoint b, mpoint c){ //judge if it is couter-colockwise
double area2 = (b.x-a.x) * (c.y-a.y) - (b.y-a.y) * (c.x-a.x);
if (area2 < 0){
return -1; // clockwise
}
else{
if (area2 > 0) return 1; // counter-clockwise
else return 0; // collinear
}
}
void get_outpoint(mpoint *points, int size){ //get points in stack
int i, k;
vector <mpoint>outpoint;
outpoint.push_back(points[0]);
outpoint.push_back(points[1]);
i = 2;
while(true){
if(i == size){
break;
}
if(ccw(outpoint[outpoint.size() - 2], outpoint[outpoint.size() - 1], points[i]) > 0){
outpoint.push_back(points[i]);
i = i + 1;
}
else{
outpoint.pop_back();
}
}
cout << "The outpoints are: " << endl;
for(k = 0; k < outpoint.size(); k++){
cout << outpoint[k].x << " " << outpoint[k].y << endl;
}
}
|
