凸包算法Jarvis's march步进法和Graham扫描法的原理及实现

2023-10-28 08:40
文章标签 算法 实现 原理 扫描 步进 凸包 march jarvis graham

本文主要是介绍凸包算法Jarvis's march步进法和Graham扫描法的原理及实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

凸包概念

在二维欧几里得空间中，凸包可想象为一条刚好包著所有点的橡皮圈。
        用自己的话说就是在一个点集中，能够包含所有点的凸多边形（所有的点都能落入多边形的内部）。专业的描述可以通过百度百科了解。在作者Kyle Loudon的《Mastering Algorithms with C》一书的中文版中描述到一个点集的凸包是指包含该点集中的所有点的最小凸多边形。如果一个多边形内任意两点之间的连线完全包含在该多边形内，则称这个多边形是凸多边形；否则多边形就是凹的。要想画一个点集的凸包，可把它假想成一块板子上的钉子。如果用细线将最外层的钉子逐个连接起来，那么细线所围成的形状就是凸包。如下图所示a为凸包，b为凹多边形。     

如图c所示所有的黑色点表示一个点集，P1~P8表示生成生成凸包的点集。
                                                   

                                          
         在这里介绍两种求有限点集的凸包，一种Jarvis's march的步进法，另一种是Grahamd的扫描法。本文档代码实现在Qt5.7.0环境下，仅供作为参考，不保证直接拿去使用没有问题。

通用函数

1）共线情况找出距离远的点

#define SEGMENTLEN(x0,y0,x1,y1) (sqrt(pow(((x1)-(x0)), 2.0) + pow(((y1)-(y0)), 2.0)))

2）判断点的位置（上边/下边）

qreal Convex::comparePointClock(const QPointF &point_0, const QPointF &point_c, const QPointF &point_i)
{return ((point_i.x() - point_0.x())*(point_c.y() - point_0.y()) - (point_i.y() - point_0.y())*(point_c.x() - point_0.x()));
}

3）删除重复坐标

quint32 Convex::removeRepeatPoints(QVector<QPointF> &vecPoints)
{if (vecPoints.isEmpty())return 0;QVector<QPointF> tempVecPorint;tempVecPorint = vecPoints;vecPoints.clear();QPointF tempPoint;while (tempVecPorint.size()){tempPoint = tempVecPorint.at(0);tempVecPorint.removeAll(tempPoint);vecPoints.push_back(tempPoint);}return vecPoints.size();
}

4）获取最小坐标

QPointF Convex::getMinimumPoint(const QVector<QPointF> &vecPoints)
{if (vecPoints.isEmpty())return QPointF();QPointF minPoint = vecPoints.at(0);quint16 point_x = vecPoints.at(0).x(), point_y = vecPoints.at(0).y();for (QVector<QPointF>::const_iterator it = vecPoints.constBegin(); it != vecPoints.constEnd(); it++){//比较Y坐标，找Y坐标最小的if (it->y() < minPoint.y()){minPoint = (*it);}else{//Y坐标相同，找X坐标小的if (it->y() == minPoint.y() && it->x() < minPoint.x()){minPoint = (*it);}}}return minPoint;
}

Jarvis's march 步进算法，复杂度O(nH)，H为点的个数

步骤：

1）找到坐标最下的点，此点必定在凸包点集中，（如果出现纵坐标最小的点有多个，那么在这些点中找到横坐标最小的点，即点集中最左下角的点）起始点作为P_0，并把其入栈。

2）遍历点集利用向量叉积的方法判断点是在线的上边（左边）还是下边（右边），设第二个点为P_c，遍历的点为P_i。如果向量叉积结果>0说明P_i在P_0P_c连线的下边（右边），<0说明P_i在P_0P_c连线的上边(左边)，==0说明P_i在P_0P_c连线上。如果点在直线的下方则更新P_c为P_i；如果在线上的话，找到距离P_0较远的点作为P_c，然后把P_c作为P_0入栈，依次类推直到遍历一周再次到达第一个入栈的点。

具体实现源码如下：

//Jarvis's march 算法，O(nH)，H为点的个数。
qint8 Convex::getConvexHullJarvis(const QVector<QPointF> &vecSourPoints, QVector<QPointF> &vecTarPoints)
{if (vecSourPoints.isEmpty())return -1;QPointF minPoint;QPointF lowPoint, point_0, point_i, point_c;qreal count = 0,z = 0;qreal length_1, length_2;QVector<QPointF> tempVecPoint(vecSourPoints);vecTarPoints.clear();//删除重复坐标if (removeRepeatPoints(tempVecPoint) <= 0)return -1;//查找最小坐标minPoint = getMinimumPoint(tempVecPoint);lowPoint = minPoint;point_0 = lowPoint;do {//起始点point_0压入凸包点集中vecTarPoints.push_back(point_0);count = 0;for (QVector<QPointF>::iterator it = tempVecPoint.begin(); it != tempVecPoint.end(); it++){//跳过起始坐标if ((*it) == point_0)continue;count++;if (count == 1) //把第一个遍历的点作为point_c{point_c = (*it);continue;}//如果z>0则point在point_i和point_c连线的下方，z<0则point_i在连线的上方，z=0则point_i共线z = comparePointClock(point_0,point_c,(*it));//((it->x() - point_0.x())*(point_c.y() - point_0.y()) - (it->y() - point_0.y())*(point_c.x() - point_0.x()));if (z > 0){point_c = (*it);}else if (z == 0){//共线情况找出距离point_0较远的那个点作为point_clength_1 = SEGMENTLEN(point_0.x(),point_0.y(),it->x(),it->y());length_2 = SEGMENTLEN(point_0.x(), point_0.y(), point_c.x(), point_c.y());if (length_1 > length_2){point_c = (*it);}}}point_0 = point_c;} while (point_0 != lowPoint);vecTarPoints.push_back(lowPoint);if (vecTarPoints.isEmpty())return -1;return 0;
}

Graham 扫描算法，复杂度O(nlgn)

步骤：

1）与Jarvis's march算法一样找到坐标最下的点作为P_0。

2）对一批无序的点集中的点按照极角从小到大进行排序，如果极角相同则按由近及远进行排序（以P_0为起始点）。

按极角从小到大进行排序：

QPointF m_point0;
bool comPolarAngle(const QPointF &point_1, const QPointF &point_2)
{qreal z = ((point_2.x() - m_point0.x())*(point_1.y() - m_point0.y()) - (point_2.y() - m_point0.y())*(point_1.x() - m_point0.x()));if (fabs(z) < 1e-6){qreal length_1 = SEGMENTLEN(m_point0.x(), m_point0.y(), point_1.x(), point_1.y());qreal length_2 = SEGMENTLEN(m_point0.x(), m_point0.y(), point_2.x(), point_2.y());return length_1 > length_2;}else{return z < 0;}
}
bool Convex::sortByPolarAngle(QVector<QPointF> &vecPoints)
{if (vecPoints.isEmpty())return false;QVector<QPointF> tempVecPoint(vecPoints);tempVecPoint.removeOne(m_point0);qreal z = 0;qSort(tempVecPoint.begin(), tempVecPoint.end(), comPolarAngle);tempVecPoint.push_front(m_point0);vecPoints = tempVecPoint;return true;
}

3）让排序后的点集中的前三个点依次入栈，然后开始遍历其后点，如果其后点与栈顶两个点不构成向左旋转的关系，则弹出栈顶元素，直到没有点需要出栈，那么就将当前点入栈，依次循环直到算有点都遍历结束。

具体实现源码：

//Graham 扫描算法，O(nlgn)。
qint8 Convex::getConvecHullGraham(const QVector<QPointF> &vecSourPoints, QVector<QPointF> &vecTarPoints)
{if (vecSourPoints.isEmpty())return -1;QVector<QPointF> tempVecPoint(vecSourPoints);//删除重复坐标if (removeRepeatPoints(tempVecPoint) <= 0)return -1;//查找最小坐标QPointF minPoint;minPoint = getMinimumPoint(tempVecPoint);m_point0 = minPoint;//按极角进行排序if(!sortByPolarAngle(tempVecPoint))return -1;vecTarPoints.clear();vecTarPoints.push_back(tempVecPoint.at(0));vecTarPoints.push_back(tempVecPoint.at(1));vecTarPoints.push_back(tempVecPoint.at(2));qint32 vecTop = 2;for (int i = 3; i < tempVecPoint.size(); i++){while (vecTop > 0&& (comparePointClock(vecTarPoints.at(vecTop - 1), vecTarPoints.at(vecTop), tempVecPoint.at(i)) >= 0)){vecTop--;vecTarPoints.pop_back();}vecTarPoints.push_back(tempVecPoint.at(i));vecTop++;}vecTarPoints.push_back(minPoint);if (vecTarPoints.isEmpty())return -1;return 0;
}

注：源码.h和.cpp文件请在本人GitHub中浏览，望与参考的人一起学习进步！

地址：https://github.com/CMwshuai/ConvexHull.git

这篇关于凸包算法Jarvis's march步进法和Graham扫描法的原理及实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/292042。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
hdu4407(容斥原理)

hdu4407(容斥原理)

题意：给一串数字1,2，......n，两个操作:1、修改第k个数字，2、查询区间[l,r]中与n互质的数之和。 解题思路：咱一看，像线段树，但是如果用线段树做，那么每个区间一定要记录所有的素因子，这样会超内存。然后我就做不来了。后来看了题解，原来是用容斥原理来做的。还记得这道题目吗？求区间[1,r]中与p互质的数的个数，如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2