凸包算法(convex hull)

前言

今天学习了几何算法——凸包算法，听着名字很奇怪，不知道它是干什么的，但其实也很简单。下面来介绍一下这种凸包算法和其c++代码：

凸包算法

其实很简单，就是用一个的凸多边形围住所有的点。就好像桌面上有许多图钉，用一根紧绷的橡皮筋将它们全部围起来一样。算法详细步骤：

1. 找到所有点中纵坐标y最小的点，也就是这些点中最下面的点，记为p0。

2. 然后计算其余点与该点的连线与x轴之间夹角的余弦值，将这些点按其对于最低点的正弦值从大到小排序，排序好的点记为p1, p2, p3, ……

3. 将最低点p0和排序好的点中的第一个点p1压入栈中，然后从p2开始计算，计算栈顶两个点与该点三点向量是否是逆时针转动，若是，则将该点压入栈中，否则将栈顶元素推出。（此处对栈的概念不清楚可自行搜索）

4. 最后栈里面元素就是所有的凸包外围的点

判断是否为逆时针旋转

area = (b.x-a.x) * (c.y-a.y) – (b.y-a.y) * (c.x-a.x)

来看看c++代码：

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 
  
    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; } } 
  

这里主要介绍算法，就没有写栈，用一个vector代替了栈，意思相同。

运行一下：

#include 
  
    #include 
   
     #include 
    
      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; } miny_point_id = get_miny_point_id(points, size); get_cos(points, mcos, miny_point_id, size); sort_points(points, mcos, size); get_outpoint(points, size); } 
     
    
  

输入：

Please input the size: 8

1 0

0 1

0 -1

-1 0

2 0

0 2

0 -2

-2 0

输出：(凸包顶点坐标)

0  -2

2  0

0  2

-2 0

总结

在图形学中，凸包是一个非常重要的概念。简明的说，在平面中给出N个点，找出一个由其中某些点作为顶点组成的凸多边形，恰好能围住所有的N个点。该凸包算法又叫Graham Scan法。点排序时间复杂度O(nlogn)， 检查每个点O(n)， 综合时间复杂度O(nlogn).

最后强烈推荐Coursera上普林斯顿大学的算法课点击打开链接

以上内容纯属个人学习总结，不代表任何团体或单位。若有理解不到之处请见谅！