凸包算法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。

相关文章

golang版本升级如何实现

golang版本升级如何实现

《golang版本升级如何实现》：本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola
阅读更多...
SpringBoot中SM2公钥加密、私钥解密的实现示例详解

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具
阅读更多...
Mysql实现范围分区表(新增、删除、重组、查看)

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型（范围、哈希、列表、键值）,主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区（Range Partitioning1、新建分区表：2、分
阅读更多...
MySQL 定时新增分区的实现示例

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后，有时候会需要自动创建分区。比如，一些表数据量非常大，有些数据是热点数据，按照日期分区MululbU
阅读更多...
MySQL中查找重复值的实现

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一：使用GROUP BY和HAVING子句方法二：仅返回重复值方法三：返回完整记录方法四：
阅读更多...
IDEA中新建/切换Git分支的实现步骤

IDEA中新建/切换Git分支的实现步骤

《IDEA中新建/切换Git分支的实现步骤》本文主要介绍了IDEA中新建/切换Git分支的实现步骤,通过菜单创建新分支并选择是否切换,创建后在Git详情或右键Checkout中切换分支,感兴趣的可以了... 前提：项目已被Git托管1、点击上方栏Git->NewBrancjsh...2、输入新的分支的
阅读更多...
Python实现对阿里云OSS对象存储的操作详解

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os
阅读更多...
关于集合与数组转换实现方法

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》：本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方
阅读更多...
从原理到实战深入理解Java 断言assert

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言（assert）：从原理到实战引言：为什么需要断言？一、断言基础1.1 语
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2