c++凸包分治算法-凸包（ConvexHull）问题的三种解法：暴力GrahamScan分治

1、c+_ConvexHull）问题的三种解法：暴GrahamScan，分治#include#include#include#include#include#include#include#include#includeusing namespace std;using namespace cv;#define e 3.3621e-4932Point2f pmin;bool SameSide(Point2f A,Point2f B,Point2f C,Point2f P)long double k = (long double)(A.y - B.y) / (A.x - B.x);long doub

2、le b = A.y - k * A.x;if (C.y - k*C.x - b = e & P.y - k*P.x - b = e) | (C.y - k*C.x - b = e & P.y - k*P.x - b = e)return true;elsereturn false;bool PointinTriangle1(Point2f A,Point2f B,Point2f C,Point2f P)return SameSide(A, B,C,P) & SameSide(B, C,A,P) & SameSide(C, A,B,P);bool cmpBy_yr(Point2f a, Poi

3、nt2f b)return a.y b.y;bool cmpBy_x(Point2f a, Point2f b)return a.x 0 | (v1 = 0 & m1 m2);void drawLine(vector points, vector p)vector left, right;int num = p.size();int miny_index = 0,maxy_index = 0;float k, b;Mat Draw_Convex_Hull(600, 600,CV_8UC3,Scalar(255, 255,255);for (int i = 0;i points.size();

4、i+)circle(Draw_Convex_Hull, pointsi, 1,Scalar(0, 0,0),1);for (int i = 0;i num;i+)if (pi.y pmaxy_index.y)maxy_index = i;k = (pmaxy_index.y - pminy_index.y) / (pmaxy_index.x - pminy_index.x);b = pmaxy_index.y - k*pmaxy_index.x;for (int i = 0;i 0)left.push_back(pi);elseright.push_back(pi);sort(right.be

5、gin(), right.end(), cmpBy_yr);sort(left.begin(), left.end(), cmpBy_yl);for (int i = 0;i right.size() - 1;i+)line(Draw_Convex_Hull,righti,righti+1, Scalar(0, 0,255),2);waitKey(30);for (int i = 0;i left.size() - 1;i+)line(Draw_Convex_Hull, lefti, lefti + 1, Scalar(0, 0,255),2);waitKey(30);line(Draw_Co

6、nvex_Hull, rightright.size() - 1, left0, Scalar(0, 0,255),2);line(Draw_Convex_Hull, leftleft.size() - 1, right0, Scalar(0, 0,255),2);imshow(Convex Hull, Draw_Convex_Hull);waitKey(0);void bruteForce(vector &p,vector &vec)int num = p.size();int min_index = 0;Point2f min = p0, tmp;vector flag(num,true)

7、;for (int i = 1;i num;i+)if (pi.y min.y)|(pi.y = min.y & pi.x min.x)min = pi;min_index = i;tmp = p0;p0 = min;pmin_index = tmp;vec.push_back(p0);for(int i = 1;i num;i+)for(int j = 0;j num;j+)for (int k = j+1; k num;k+)if (i != j&i != k)if (PointinTriangle1(pj, pk, p0, pi)flagi = false;for (int i = 1;

8、i num;i+)if (flagi)vec.push_back(pi);void grahamScan(vector &p,vector &vec)vector ang;int num = p.size();int min_index = 0;Point2f min = p0, tmp ,top1, top;vector flag(num, true);for (int i = 1;i num;i+)if (pi.y min.y) | (pi.y = min.y & pi.x min.x)min = pi;min_index = i;tmp = p0;p0 = min;pmin = min;

9、pmin_index = tmp;vec.push_back(p0);sort(p.begin() + 1,p.end(), cmpBy_ang);vec.push_back(p1);vec.push_back(p2);for (int i = 3;i 2)vec.pop_back();vec.push_back(pi);void Divide_Conquer(vector &p,int l, int r, vector &vec)if (r - l 3)return;if (r - l = 3)vec.insert(vec.end(), p.begin() + l, p.begin() +

10、r + 1);return;double countx = 0;for (int i = l; i = r; i+)countx += pi.x;countx /= (r - l + 1);int k = (l + r) / 2;vector temp_left, temp_right, answer;Divide_Conquer(p, k + 1,r, temp_right);Divide_Conquer(p, l, k, temp_left);temp_left.insert(temp_left.end(), temp_right.begin(), temp_right.end();gra

11、hamScan(p, answer);vec.insert(vec.end(),answer.begin(),answer.end();void Divide_Conquer_Warp(vector &p,vector &vec)sort(p.begin(), p.end(), cmpBy_x);Divide_Conquer(p, 0,p.size() - 1,vec);int main()float x, y;int num = 100;vector vp2f;vector con_hull;LARGE_INTEGER t1, t2, tc;QueryPerformanceFrequency

12、(&tc);srand(time(NULL);for (int i = 0;i num;i+)x = rand()*1. / (RAND_MAX / 500.);y = rand()*1. / (RAND_MAX / 500.);vp2f.push_back(Point2f(x, y);/bruteForce/* QueryPerformanceCounter(&t1); bruteForce(vp2f,con_hull); QueryPerformanceCounter(&t2); cout Point Numbers: num t Time of Brute Force： (t2.Quad

13、Part - t1.QuadPart)*1.0 / tc.QuadPart endl;drawLine(vp2f,con_hull);*/ Graham ScanQueryPerformanceCounter(&t1);grahamScan(vp2f, con_hull);QueryPerformanceCounter(&t2);cout Point Numbers: num t Time of Graham_Scan： (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart endl;drawLine(vp2f, con_hull);/ Divide and Conquer/* QueryPerformanceCounter(&t1