凸包2——Graham算法

刺骨的言语ヽ痛彻心扉 2021-11-11 11:44 355阅读 0赞

**1.点集排序**

为了得到加入新点的顺序 Graham扫描法的第一步是对点集排序

排序是对杂乱的点集进行了**梳理** 这也是这种算法能够得到更高效率的根本原因

排序的方法也有两种 **极角坐标排序(极角序)** 和 **直角坐标排序(水平序)**

前者**好理解**一些 但是在实现的时候 后者**更方便**

先说极角序 为了极角排序 我们先得得到一个参考点

一般的 我们取最左边(横坐标最小)的点作为**参考点** 如果有多个这样的点就取最下面的(纵坐标最小)

看这样一个例子 这是一个任意给出的平面点集:

![2011031017121366.png][]

参考点的**定义**:在**横坐标最小**的情况下取**纵坐标最小**的点

所以所有的点只能在这个**黄色的半平面**中 而且**正上方为闭(可取得) 正下方为开(不可取)**

这就决定了参考点的**性质**:点集中**任意两点**和参考点所成的到角为**锐角**

这样我们取得参考点 然后再考虑极角排序

**![2011031017221378.png][]**

极角排序以参考点为**极角坐标系原点** 各个点的**极角**为关键字

由于上面我们得到的参考点的性质 我们可以设所有点的极角**均在(-90,90\]之间**

排序完成后应该是这样的:

![2011031017323131.png][]

比较极角我们仍然可以利用**向量的叉积**

同样由于参考点的性质 所有向量之间的到角都是在**180度以内** 不会产生错误

![2011031017491387.png][]

转载于:https://www.cnblogs.com/o8le/archive/2011/11/15/2250115.html

[2011031017121366.png]: /images/20211109/bce449af06764a46a2b6bfb8035c7606.png
[2011031017221378.png]: /images/20211109/163e422b35e4448aa2c2284ef3d08d0a.png
[2011031017323131.png]: /images/20211109/7cfa30d79f414781a61ffba56c6c2b2d.png
[2011031017491387.png]: /images/20211109/0b646a1ab6e74aa18bbafd06dbb34842.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 [Python凸包算法实现条形码检测]——利用OpenCV和凸包算法进行条形码识别

\[Python凸包算法实现条形码检测\]——利用OpenCV和凸包算法进行条形码识别在图像处理中，条形码检测是一个重要的应用场景。本文将介绍如何利用 Python 的 O

末蓝、/ 2024年03月25日 21:51/ 0 赞/ 90 阅读

相关 POJ 1113-Wall（凸包-Graham算法）

Wall <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

悠悠/ 2022年09月26日 11:51/ 0 赞/ 191 阅读

相关计算几何-经典算法-凸包

[计算几何-经典算法-凸包][-_-] 　　在学习了一些有关计算机几何的基础知识和一些基本工具之后要快速的解决一些简单的几何问题，如两点之间的距离、两线段的交点个数等等是

左手的ㄟ右手/ 2022年08月12日 00:17/ 0 赞/ 260 阅读

相关 POJ 2187-Beauty Contest（凸包-Graham扫描法/旋转卡壳法）

Beauty Contest <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000

刺骨的言语ヽ痛彻心扉/ 2022年07月11日 05:49/ 0 赞/ 233 阅读

相关二维凸包模板(Graham算法)

时间复杂度O(nlogn) 模板： include <cstdio> include <cmath> include <cstdlib>

矫情吗；*/ 2022年06月11日 09:26/ 0 赞/ 262 阅读

相关 OpenCV凸包凸缺陷检测

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

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

相关算法三十二：凸包

描述给定n个二维平面上的点，求他们的凸包。输入第一行包含一个正整数n。接下来n行，每行包含两个整数x,y，表示一个点的坐标。输出令所有在凸包

比眉伴天荒/ 2022年05月21日 09:11/ 0 赞/ 246 阅读

相关凸包1——卷包裹算法

有了向量我们就可以选取一个最外侧的点了 ![2011022818131866.png][] 利用向量我们可以比较哪个点"更外侧" 比如点K和点I 我们利用向量J

逃离我推掉我的手/ 2021年11月11日 11:44/ 0 赞/ 314 阅读

相关凸包2——Graham算法

1.点集排序为了得到加入新点的顺序 Graham扫描法的第一步是对点集排序排序是对杂乱的点集进行了梳理这也是这种算法能够得到更高效率的根本原因排序的方法也有两种

刺骨的言语ヽ痛彻心扉/ 2021年11月11日 11:44/ 0 赞/ 356 阅读