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
| void quickHull(std::vector<Matrix<double> >&hull,std::vector<Matrix<double> >&points,Matrix<double>P1,Matrix<double>P2,int side){ int ind=-1; double max_dist=0; for (int i=0;i<(int)(points.size());++i){ double temp=lineDist(P1,P2,points[i]); if (findSide(P1,P2,points[i])==side && temp>max_dist){ ind=i,max_dist=temp; } } if (ind==-1){ hull.push_back(P1); hull.push_back(P2); return ; } quickHull(hull,points,points[ind],P1,-findSide(points[ind],P1,P2)); quickHull(hull,points,points[ind],P2,-findSide(points[ind],P2,P1)); } std::vector<Matrix<double> >hull; int min_x=0,max_x=0; for (int i=1;i<(int)(points.size());++i){ if (points[i](1)<points[min_x](1)) min_x=i; if (points[i](1)>points[max_x](1)) max_x=i; } quickHull(hull,points,points[min_x],points[max_x],1); quickHull(hull,points,points[min_x],points[max_x],-1); std::sort(hull.begin(),hull.end(),[](Matrix<double> a,Matrix<double> b){return a(1)<b(1)?true:a(2)<b(2);}); hull.erase(unique(hull.begin(),hull.end(),[](Matrix<double> a,Matrix<double> b){return a==b;}),hull.end()); return hull;
|