如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个固定的点集我们需要找到该点集的凸包。此外我们还需要找到从该点集中移除一个点后得到的凸包。例子初始点集(-2, 8) (-1, 2) (0, 1) (1, 0)(-3, 0) (-1, -9) (2, -6) (3, 0)(5, 3) (2, 5)初始凸包(-2, 8) (-3, 0) (-1, -9) (2, -6)(5, 3)从点集中移除的点(-2, 8)最终凸包(2, 5) (-3, 0) (-1, -9) (2, -6) (5, 3)前提条件凸包简单的分治算法JavaScript 利用分治算法求凸包https://blog.csdn.net/hefeng_aspnet/article/details/160184183C# 利用分治算法求凸包https://blog.csdn.net/hefeng_aspnet/article/details/160184134Python 利用分治算法求凸包https://blog.csdn.net/hefeng_aspnet/article/details/160184105Java 利用分治算法求凸包https://blog.csdn.net/hefeng_aspnet/article/details/160184068C 利用分治算法求凸包https://blog.csdn.net/hefeng_aspnet/article/details/160182615解决上述问题的算法非常简单。我们只需检查要移除的点是否属于凸包。如果是则必须从初始集合中移除该点然后重新构建凸包参见上面凸包分治。如果不是这样那么我们已经有了解决方案凸包不会改变。// C program to demonstrate delete operation// on Convex Hull.#includebits/stdc.husing namespace std;// stores the center of polygon (It is made// global because it is used in compare function)pairint, int mid;// determines the quadrant of a point// (used in compare())int quad(pairint, int p){if (p.first 0 p.second 0)return 1;if (p.first 0 p.second 0)return 2;if (p.first 0 p.second 0)return 3;return 4;}// Checks whether the line is crossing the polygonint orientation(pairint, int a, pairint, int b,pairint, int c){int res (b.second-a.second)*(c.first-b.first) -(c.second-b.second)*(b.first-a.first);if (res 0)return 0;if (res 0)return 1;return -1;}// compare function for sortingbool compare(pairint, int p1, pairint, int q1){pairint, int p make_pair(p1.first - mid.first,p1.second - mid.second);pairint, int q make_pair(q1.first - mid.first,q1.second - mid.second);int one quad(p);int two quad(q);if (one ! two)return (one two);return (p.second*q.first q.second*p.first);}// Finds upper tangent of two polygons a and b// represented as two vectors.vectorpairint, int merger(vectorpairint, int a,vectorpairint, int b){// n1 - number of points in polygon a// n2 - number of points in polygon bint n1 a.size(), n2 b.size();int ia 0, ib 0;for (int i1; in1; i)if (a[i].first a[ia].first)ia i;// ib - leftmost point of bfor (int i1; in2; i)if (b[i].first b[ib].first)ibi;// finding the upper tangentint inda ia, indb ib;bool done 0;while (!done){done 1;while (orientation(b[indb], a[inda], a[(inda1)%n1]) 0)inda (inda 1) % n1;while (orientation(a[inda], b[indb], b[(n2indb-1)%n2]) 0){indb (n2indb-1)%n2;done 0;}}int uppera inda, upperb indb;inda ia, indbib;done 0;int g 0;while (!done)//finding the lower tangent{done 1;while (orientation(a[inda], b[indb], b[(indb1)%n2])0)indb(indb1)%n2;while (orientation(b[indb], a[inda], a[(n1inda-1)%n1])0){inda(n1inda-1)%n1;done0;}}int lowera inda, lowerb indb;vectorpairint, int ret;//ret contains the convex hull after merging the two convex hulls//with the points sorted in anti-clockwise orderint ind uppera;ret.push_back(a[uppera]);while (ind ! lowera){ind (ind1)%n1;ret.push_back(a[ind]);}ind lowerb;ret.push_back(b[lowerb]);while (ind ! upperb){ind (ind1)%n2;ret.push_back(b[ind]);}return ret;}// Brute force algorithm to find convex hull for a set// of less than 6 pointsvectorpairint, int bruteHull(vectorpairint, int a){// Take any pair of points from the set and check// whether it is the edge of the convex hull or not.// if all the remaining points are on the same side// of the line then the line is the edge of convex// hull otherwise notsetpairint, int s;for (int i0; ia.size(); i){for (int ji1; ja.size(); j){int x1 a[i].first, x2 a[j].first;int y1 a[i].second, y2 a[j].second;int a1 y1-y2;int b1 x2-x1;int c1 x1*y2-y1*x2;int pos 0, neg 0;for (int k0; ka.size(); k){if (a1*a[k].firstb1*a[k].secondc1 0)neg;if (a1*a[k].firstb1*a[k].secondc1 0)pos;}if (pos a.size() || neg a.size()){s.insert(a[i]);s.insert(a[j]);}}}vectorpairint, int ret;for (auto e : s)ret.push_back(e);// Sorting the points in the anti-clockwise ordermid {0, 0};int n ret.size();for (int i0; in; i){mid.first ret[i].first;mid.second ret[i].second;ret[i].first * n;ret[i].second * n;}sort(ret.begin(), ret.end(), compare);for (int i0; in; i)ret[i] make_pair(ret[i].first/n, ret[i].second/n);return ret;}// Returns the convex hull for the given set of pointsvectorpairint, int findHull(vectorpairint, int a){// If the number of points is less than 6 then the// function uses the brute algorithm to find the// convex hullif (a.size() 5)return bruteHull(a);// left contains the left half points// right contains the right half pointsvectorpairint, intleft, right;for (int i0; ia.size()/2; i)left.push_back(a[i]);for (int ia.size()/2; ia.size(); i)right.push_back(a[i]);// convex hull for the left and right setsvectorpairint, intleft_hull findHull(left);vectorpairint, intright_hull findHull(right);// merging the convex hullsreturn merger(left_hull, right_hull);}// Returns the convex hull for the given set of points after// removing a point p.vectorpairint, int removePoint(vectorpairint, int a,vectorpairint, int hull,pairint, int p){// checking whether the point is a part of the// convex hull or not.bool found 0;for (int i0; i hull.size() !found; i)if (hull[i].first p.first hull[i].second p.second)found 1;// If point is not part of convex hullif (found 0)return hull;// if it is the part of the convex hull then// we remove the point and again make the convex hull// and if not, we print the same convex hull.for (int i0; ia.size(); i){if (a[i].firstp.first a[i].secondp.second){a.erase(a.begin()i);break;}}sort(a.begin(), a.end());return findHull(a);}// Driver codeint main(){vectorpairint, int a;a.push_back(make_pair(0, 0));a.push_back(make_pair(1, -4));a.push_back(make_pair(-1, -5));a.push_back(make_pair(-5, -3));a.push_back(make_pair(-3, -1));a.push_back(make_pair(-1, -3));a.push_back(make_pair(-2, -2));a.push_back(make_pair(-1, -1));a.push_back(make_pair(-2, -1));a.push_back(make_pair(-1, 1));int n a.size();// sorting the set of points according// to the x-coordinatesort(a.begin(), a.end());vectorpairint, int hull findHull(a);cout Convex hull:\n;for (auto e : hull)cout e.first e.second endl;pairint, int p make_pair(-5, -3);removePoint(a, hull, p);cout \nModified Convex Hull:\n;for (auto e:hull)cout e.first e.second endl;return 0;}输出凸包(convex hull)-3 0-1 -92 -65 32 5时间复杂度很容易看出每次查询所花费的最大时间是构建凸包所需的时间即 O(n*logn)。因此总复杂度为 O(q*n*logn)其中 q 为要删除的点数。辅助空间O(n)因为占用了 n 个额外的空间。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。