抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

Divide and Conquer

Similar to quick sort

image-20230126100812125

2D Implementation

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;

评论