格雷厄姆扫描法是利用平面上任意3 点所构成的回路是左转还是右转的判别法来求平面点集的凸包。
1.三角区符号的计算
点o(a,b),p(c,d),q(e,f)是平面上的任意三点,D=ab+cf+eb-bc-de-fa
当D 为正时,o,p,q,o 构成一个反时针方向的回路,即o,p,q,是左转的;当D 为负时,o,p,q,o 构成一个顺时针方向的回路,即o,p,q 是右转的;当D 为零时,此三点共线。
3.算法步骤:
(1)求平面点集S 中Y 坐标最小的点p0。
(2)以p0 为源点,变换S-{p0}中所有点的坐标
(3)以p0 为源点,计算S-{p0}中所有点的幅角。
(4)以幅角的非降排序S-{p0}中所有的点,令事件调度点T={p1,p2,…, pn-1}是排序过的数组。
(5)初始化堆栈:令CHS[0]=pn-1,CHS[1]=p0;令堆栈指针sp=1,事件调度点数组T的下标k=0。
(6)如果k<n-1,转步骤(7);否则,算法结束。
(7)计算CHS[sp -1], CHS[sp]= p0 ,T[k]所构成的三角区符号D,若D>= 0,sp= sp+1,CHS[sp] =T[k],k=k+1,转步骤(6);否则,sp=sp-1;转步骤(6)。
算法实现
分享到:
相关推荐
采用Graham扫描法,实现提取凸包最小边界JS代码实现。(代码中点坐标采用平面坐标,如要在三维贴地展示,可转换为经纬度坐标)
NULL 博文链接:https://128kj.iteye.com/blog/1749114
用VS2010写的Graham扫描法求解凸包问题 包括两个库文件和一个主文件 两个库文件包括凸包问题中栈的基本操作以及用到的一些点的运算函数 主函数中包含了程序的主要流程
一般有两种算法来计算平面上给定n个点的凸包:Graham扫描法(Graham’s scan),时间复杂度为O(nlgn);Jarvis步进法(Jarvis march),时间复杂度为O(nh),其中h为凸包顶点的个数。这两种算法都按逆时针方向输出凸包顶点...
采用c++进行编程的凸包算法,是和生长算法不同的另一种构建tin的算法,该算法相对难度较大,此处用的是Graham扫描法
grahamScan扫描法求凸包 输入有若干组测试数据。每一组测试数据的第一行上有整数n,表示该组测试数据有n个点组成的。接下来有n行,其每一行上有二个正整数,之间用一个或几个空格隔开。当输入行上只有一个数0时,...
凸包最常用的凸包算法是Graham扫描法和Jarvis步进法 本程序用Graham扫描法实现凸包的绘制
求凸包(Graham扫描法): 旋转卡壳法: Image_BWLabel(Python): Two-Pass法: Image_DFT_IDFT(C++): Image_FFT_IFFT(C++): : Image_Hough(C++): : Image_Radon(C++): : Image_White_Balance(C++): 灰度世界算法...
方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网。结果通过500至10000个点的测试,表明这种基于C-...
一、数学问题 1.精度计算——大数阶乘.乘法.加法.减法 .任意进制转换.最大公约数、最小公倍数....计算几何.Graham扫描法寻找凸包 .数论.求解模线性方程 图论.Dijkstra算法求单源最短路径.数据结构 。
Graham扫描法 水平序的引进,共线凸包的补丁 完美凸包算法 相关判定 两直线相交 两线段相交 点在任意多边形内的判定 点在凸多边形内的判定 经典问题 最小外接圆 近似O(n)的最小外接圆算法 点集直径 ...
12.Graham扫描法寻找凸包 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7.判断一...
12.Graham扫描法寻找凸包 13.求两条线段的交点 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7....
凸包算法(Graham扫描法) Graham-Scan 辗转相除法求最大公约数 Greatest-Common-Divisor 堆排序 Heap-Sort ISAP算法 Improved-Shortest-Augmenting-Path(Naive) 插入排序 Insertion-Sort 字符串匹配(KMP) ...
8.4.3 Graham扫描算法 8.5 最近点对 8.6 水平线段和竖直线段的交点 8.7 小结 第9章 代数和数值算法 9.1 引言 9.2 求幂运算 9.3 欧几里得算法 9.4 多项式乘法 9.5 矩阵乘法 9.5.1 Winograd算法 9.5.2 ...
12.Graham扫描法寻找凸包 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7.判断一个数是否素数 ...
该算法首先使用Canny算子提取叶片轮廓,然后使用基于平面扫描法的Graham算法构造叶片轮廓凸包,最后提取叶片最小外接矩形。仿真实验结果表明:在Flavia植物叶片数据库中进行测试,该算法优于旋转法、顶点链码法。
| GRAHAM 求凸包 O(N * LOGN) 34 | 判断线段相交 34 | 求多边形重心 34 | 三角形几个重要的点 34 | 平面最近点对 O(N * LOGN) 34 | LIUCTIC 的计算几何库 35 | 求平面上两点之间的距离 35 | (P1-P0)*(P2-P0)...