C++ 从凸包中删除点(Deleting points from Convex Hull)-北京尧图网络

如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个固定的点集我们需要找到该点集的凸包。此外我们还需要找到从该点集中移除一个点后得到的凸包。例子初始点集(-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 个额外的空间。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。

C++ 从凸包中删除点(Deleting points from Convex Hull)

相关推荐

动态权重驱动的混合向量检索实践：破解多维度异构数据检索的精度与效率难题

Windows 11专业版Docker安装与AI开发环境配置全攻略

Potree：WebGL点云渲染引擎的技术演进与智能可视化未来

更多资讯

机械臂坐标系变换：从旋转矩阵到DH参数与正运动学

GIS数据驱动UE程序化生成数字孪生周边建筑全流程指南

基于PaddleNLP的统一生成式模型：汽车问答摘要与推理实战

跨链技术架构详解：从物理部署到协议选型的工程实践

Vue+TS双端答题系统源码拆解：工程结构与组件化实践

MySQLdb 安装教程，这次用 TaoToken 让 Codex 走通依赖安装

今日更新

基于高阶循环谱的MPSK载波频率估计与MATLAB实现

MiniPdf方：.NET开源Office转PDF的高效解决方案

Solon AI v3.10：Java全栈智能体开发框架解析

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？