凸包问题之GrahamScan解法

素颜马尾好姑娘i 2022-08-01 06:21 156阅读 0赞

首先了解一下GrahamScan解法的原理：

当沿着 Convex hull 逆时针漫游时，总是向左转 在极坐标系下按照极角大小排列，然后逆时针 方向漫游点集，去除非 Convex hull 顶点 ( 非左  转点 ) 。

第一步

![Center][]

这里P0是极坐标的中心，在编程的时候，经常就是选择y坐标最低的点

第二步：

![Center 1][]

这样就建立起了所有点到P0的极坐标

第三步：

![Center 2][]

这里首先选择三个点压栈，这三个点肯定构成的是非右转关系

看P3

![Center 3][]

可以发现P3和P2P1构成右转关系，因此考虑把P2从凸包点中排除，然后把P3加入到凸包栈中，继续向前探进

第四步：

![Center 4][]

这里P3P4P5都不构成右转，因此都放入到凸包栈中，

第五步：

![Center 5][]

P6P5P4构成右转关系，因此需要删除P5，加入P6，

![Center 6][]

P7P6P4构成右转关系，因此删除P6，加入P7，P7P4P3构成非右转关系，删除P4。。。。。。。

知道所有点都遍历完

第七步：

![Center 7][]

上图构成的就是凸包了（包括P0）

![20150621150410285][]

[Center]: /images/20220731/5bd0b22da37e4990b1f5702c687f0548.png
[Center 1]: /images/20220731/e2829e5e5c054c53865ada58673796d4.png
[Center 2]: /images/20220731/051d41e0ea9d47ef9f903caf4fa86fa0.png
[Center 3]: /images/20220731/e74a64be466246fbaab7fa8603b90013.png
[Center 4]: /images/20220731/117ac120afb44e9fbfe2cd6fd36098a0.png
[Center 5]: /images/20220731/ac21f1e098a34d52bc0f0465d1b288f6.png
[Center 6]: /images/20220731/6ec9f1356ff946ad9a312f1a1eed75e7.png
[Center 7]: /images/20220731/7a4616258c4c44ff81b041377a006e1b.png
[20150621150410285]: /images/20220731/b5c3cc36c7bb4ed4b664234b6ce2e83e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python OpenCV 凸包：使用OpenCV实现凸包算法

Python OpenCV 凸包：使用OpenCV实现凸包算法在图像处理中，我们经常需要对图像中的轮廓进行分析和处理。而在轮廓处理中，凸包算法是一种十分重要的技术。Pyth

冷不防/ 2024年03月25日 23:50/ 0 赞/ 68 阅读

相关 Acwing 2935：信用卡凸包（计算几何问题转化 + 凸包）

原题链接传送门：[Acwing 2935：信用卡凸包][Acwing 2935] 题目大意给n张信用卡，每张大小都一样，然后给每张卡的四角进行圆滑处理，即割一

短命女/ 2022年11月06日 14:00/ 0 赞/ 255 阅读

相关 opencv获取凸包

import cv2 import numpy as np def gettubao(imgray): img = np.ze

「爱情、让人受尽委屈。」/ 2022年10月16日 03:56/ 0 赞/ 215 阅读

相关 1012 寻找凸包

Description 给定平面上N个点, 请找出这N个点的凸包. Input 第一行输入M表示包含M组测试数据，每组先输入N (N<=100), 接着输

Dear 丶/ 2022年09月11日 15:21/ 0 赞/ 254 阅读

相关计算几何-凸包问题

问题给定平面上的二维点集，求解其凸包。一、Graham扫描法 1. 在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取

深碍√TFBOYSˉ_/ 2022年08月06日 02:27/ 0 赞/ 247 阅读

相关凸包问题之GrahamScan解法

首先了解一下GrahamScan解法的原理：当沿着 Convex hull 逆时针漫游时，总是向左转在极坐标系下按照极角大小排列，然后逆时针方向漫游点集，去除非 Con

素颜马尾好姑娘i/ 2022年08月01日 06:21/ 0 赞/ 157 阅读

相关 OpenCV凸包凸缺陷检测

![20170930235136628][] 左边原图，右边结果。右图中，蓝色线为凸包，凸缺陷的起始点为黑色点，凸缺陷的起始点为绿色点，凸缺陷的最深点为红色点（即边缘点到

逃离我推掉我的手/ 2022年06月07日 00:43/ 0 赞/ 601 阅读

相关凸包问题的五种解法

前言：首先，什么是凸包？假设平面上有p0~p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸

朱雀/ 2022年04月11日 02:18/ 0 赞/ 304 阅读

相关凸包（Convex Hull）

凸包介绍 -------------------- 代码 include <opencv2/opencv.hpp> include <i

柔情只为你懂/ 2022年03月22日 09:42/ 0 赞/ 331 阅读

相关寻找凸包

问题：点集 Q 的凸包 (convex hull) 是一个最小的凸多边形 P：Q 中的每个点或在 P 的边界上或在 P 的内部，我们用 CH(Q) 表示点集 Q 的凸包。问

绝地灬酷狼/ 2022年03月01日 13:56/ 0 赞/ 387 阅读