这个算法属于常见算法,原理比较容易理解,是网络书籍或其他文献资料里较为常见的,个人觉得没什么必要重新描述该算法,互联网上许多人撰写的博客应该都比我清晰易懂这里就不班门弄斧了C代码如下:#includeiostream#includevector#includealgorithm#includeutilityusingnamespacestd;inttriAngleArea(intx1,inty1,intx2,inty2,intx3,inty3)//返回(x1,y1),(x2,y2),(x3,y3)三点确定的三角形面积{returnx1*y2x3*y1x2*y3-x3*y2-x2*y1-x1*y3;}intcross(intx1,inty1,intx2,inty2)//向量(x1,y1)和(x2,y2)遵循右手定则的叉积{returnx1*y2-x2*y1;}voidgetCH(vectorpairint,intCH,pairint,intleftmost,pairint,intrightmost,vectorpairint,intpoint_list)//计算下凸包只需把第二第三个参数对调{if(point_list.empty()){CH.push_back(rightmost);CH.push_back(leftmost);return;}vectorpairint,intmax_area_point;intmax_area0;for(size_t i0;ipoint_list.size();i){intStriAngleArea(point_list[i].first,point_list[i].second,leftmost.first,leftmost.second,rightmost.first,rightmost.second);if(Smax_area){max_area_point.clear();max_areaS;max_area_point.push_back(point_list[i]);}elseif(Smax_area){max_area_point.push_back(point_list[i]);}}pairint,intmax_pointmax_area_point[0];for(size_t i1;imax_area_point.size();i){if(cross(max_area_point[i].first-leftmost.first,max_area_point[i].second-leftmost.second,max_point.first-leftmost.first,max_point.second-leftmost.second)0)max_pointmax_area_point[i];}vectorpairint,intleft_point_list;vectorpairint,intright_point_list;for(size_t i0;ipoint_list.size();i){if(point_list[i]max_point)continue;if(cross(point_list[i].first-leftmost.first,point_list[i].second-leftmost.second,max_point.first-leftmost.first,max_point.second-leftmost.second)0){left_point_list.push_back(point_list[i]);}elseif(cross(point_list[i].first-rightmost.first,point_list[i].second-rightmost.second,max_point.first-rightmost.first,max_point.second-rightmost.second)0){right_point_list.push_back(point_list[i]);}}vectorpairint,intleft_CH;getCH(left_CH,leftmost,max_point,left_point_list);vectorpairint,intright_CH;getCH(right_CH,max_point,rightmost,right_point_list);for(size_t i0;iright_CH.size();i){CH.push_back(right_CH[i]);}for(size_t i1;ileft_CH.size();i){CH.push_back(left_CH[i]);}}intmain(){vectorpairint,intCH;vectorpairint,intpoint_list{{2,6},{2,5},{1,4},{3,4},{5,4},{6,4},{1,3},{2,3},{5,3},{7,3},{0,2},{3,2},{7,2},{8,2},{2,1},{6,1},{7,1},{9,1},{4,0},{6,0},{7,0}};sort(point_list.begin(),point_list.end());size_t min_x0;size_t max_xpoint_list.size()-1;if(point_list[min_x].firstpoint_list[max_x].first){CH.push_back(point_list[0]);CH.push_back(point_list.back());}else{size_t p1_left_max;for(p1_left_max1;;p1_left_max){if(point_list[p1_left_max].first!point_list[0].first){--p1_left_max;break;}}size_t p2_right_min;for(p2_right_minpoint_list.size()-2;;--p2_right_min){if(point_list[p2_right_min].first!point_list.back().first){p2_right_min;break;}}vectorpairint,intpoint_list_up;vectorpairint,intpoint_list_down;for(size_t ip1_left_max1;ip2_right_min;i){if(cross(point_list[i].first-point_list[p1_left_max].first,point_list[i].second-point_list[p1_left_max].second,point_list[max_x].first-point_list[p1_left_max].first,point_list[max_x].second-point_list[p1_left_max].second)0)point_list_up.push_back(point_list[i]);if(cross(point_list[i].first-point_list[min_x].first,point_list[i].second-point_list[min_x].second,point_list[p2_right_min].first-point_list[min_x].first,point_list[p2_right_min].second-point_list[min_x].second)0)point_list_down.push_back(point_list[i]);}vectorpairint,intup_ch;vectorpairint,intdown_ch;getCH(up_ch,point_list[p1_left_max],point_list[max_x],point_list_up);getCH(down_ch,point_list[p2_right_min],point_list[min_x],point_list_down);boolerase_left_pointfalse;boolerase_right_pointfalse;if(p1_left_max0)erase_left_pointtrue;if(p2_right_minpoint_list.size()-1)erase_right_pointtrue;for(size_t run0;rundown_ch.size();run){if(erase_left_pointdown_ch[run]point_list[0]){continue;}if(erase_right_pointdown_ch[run]point_list.back()){continue;}CH.push_back(down_ch[run]);}for(size_t run0;runup_ch.size();run){CH.push_back(up_ch[run]);}}cout所给点集的凸包为endl;for(size_t i0;iCH.size();i){cout(CH[i].first,CH[i].second) ;}coutendl;return0;}