2D凸包算法（五）：Divide and Conquer

本文主要是介绍2D凸包算法（五）：Divide and Conquer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Divide and Conquer 图示

在这里插入图片描述
先对所有的点集进行分割成各个区域，对每个子区域进行凸包算法（如jarvis’s march）求得子凸包。
合并凸包，找到两条外公切线即可。从左凸包最右点、右凸包最左点开始，固定左端顺时针转、固定右端逆时针转，轮流前进直到符合凸包要求，且下一步就会破坏其规则为止。同理，可以得到另一半。

时间复杂度为 O(NlogN)
其中一次排序的时间，通常为 O(NlogN) ，
Divide and Conquer 向下递归O(logN) 深度，
合并凸包需要 O(N) 时间。

具体思想：

排序，便于分割区域
根据节点数均匀分割成L个区域
每块区域使用凸包算法（如jarvis’s march）求得凸包
两两进行合并，通过获得两个子区域的边界（同是内边界或同是外边界）作为起点
如图，以内边界开始，右凸包向逆时针移动，左凸包向顺时针移动。
如果右凸包向逆时针移动到下一个节点a2时，左凸包的节点b1和右凸包的上一个节点a1，a2出现了逆时针方向，则说明已经到达顶点。否者继续移动
同理，如果左凸包向顺时针移动到下一个节点b2时，右凸包的节点a1和左凸包的上一个节点b1，b2出现了顺时针方向，则说明已经到达顶点。否者继续移动
直到两凸包都到达顶点，结束下边界的生成
同样的方法生成上边界
直到所有的区域都合并完为止

在这里插入图片描述

Divide and Conquer 代码

// Finds upper tangent of two polygons 'a' and 'b' 
// represented as two vectors. 
vector<pair<double,double>> merger(vector<pair<double,double> > a, vector<pair<double,double> > b) 
{ // n1 -> number of points in polygon a // n2 -> number of points in polygon b long long int n1 = a.size();long long int n2 = b.size();//printf("line 78\n");long long int ia = 0;long long int ib = 0; for (long long int i=1; i<n1; i++) if (a[i].first > a[ia].first) ia = i; //	printf("line 84\n");// ib -> leftmost point of b for (long long int i=1; i<n2; i++) if (b[i].first < b[ib].first) ib=i; //printf("line 89\n");// finding the upper tangent long long int inda = ia;long long int indb = ib; //printf("line 94\n");bool done = 0; if(n1==0 || n2==0){done=1;}while (!done) { done = 1;//	printf("entered %lld %lld\n",n1,n2); while (orientation(b[indb], a[inda], a[(inda+1)%n1]) >=0) {//				printf("no its this one\n");inda = (inda + 1) % n1; }while (orientation(a[inda], b[indb], b[(n2+indb-1)%n2]) <=0) { 	indb = (n2+indb-1)%n2; done = 0; //printf("is this error\n");} } 
//	printf("line 106\n");long long int uppera = inda;long long int upperb = indb; inda = ia;indb=ib; done = 0; long long int g = 0; if(n1==0 || n2==0){done=1;}while (!done)//finding the lower tangent { done = 1; while (orientation(a[inda], b[indb], b[(indb+1)%n2])>=0) indb=(indb+1)%n2; while (orientation(b[indb], a[inda], a[(n1+inda-1)%n1])<=0) { inda=(n1+inda-1)%n1; done=0; } } //printf("merger\n");long long int lowera = inda;long long int lowerb = indb; vector<pair<double,double>> ret; //ret contains the convex hull after merging the two convex hulls //with the points sorted in anti-clockwise order long long int ind = uppera; ret.push_back(a[uppera]); while (ind != lowera) { ind = (ind+1)%n1; ret.push_back(a[ind]); } ind = lowerb; ret.push_back(b[lowerb]); while (ind != upperb) { ind = (ind+1)%n2; ret.push_back(b[ind]); } return ret; } // Returns the convex hull for the given set of points 
vector<pair<double, double>> divide(vector<pair<double,double>> a) 
{ // If the number of points is less than 6 then the // function uses the brute algorithm to find the // convex hull if (a.size() <= 10) {return jarvis_march(a); }// left contains the left half points // right contains the right half points vector<pair<double,double>>left, right; for (long long int i=0; i<a.size()/2; i++) left.push_back(a[i]); for (long long int i=a.size()/2; i<a.size(); i++) right.push_back(a[i]); // convex hull for the left and right sets vector<pair<double,double>>left_hull = divide(left); vector<pair<double,double>>right_hull = divide(right); //printf("completed till here\n");// merging the convex hulls return merger(left_hull, right_hull); 
}