- 浏览: 494982 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
jkxydp:
算法运行的结果根本就不对。
BM算法. -
soarwindzhang:
感谢博主的分享,我今天看了您的UFSET非递归的路径压缩时感觉 ...
并查集 -
zhangning290:
楼主好像只考虑了坏字符规则,。没有考虑好后缀
BM算法. -
lsm0622:
文字描述有错误 误导新学者
求有向图的强连通分量(scc):Tarjan算法 -
knightchen:
博主,你太强了!这篇文章对我学习C++多线程很有帮助!谢谢
并发学习之一_windows下ZThread在CodeBlocks上的安装与配置
1,点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上或者在其内。
2,凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。
3,Graham扫描法:
首先,找到所有点中最左边的(y坐标最小的),如果y坐标相同,找x坐标最小的.
以这个点为基准求所有点的极角(atan2(y-y0,x-x0)),并按照极角对这些点排序,前述基准点在最前面,设这些点为P[0]..P[n-1.
注:这样预处理后,保证p[0],p[1]和p[n-1]都是凸包上的点.
建立一个栈,初始时P[0]、P[1]、P[2]进栈,对于 P[3..n-1]的每个点,若栈顶的两个点与它不构成"向左转"的关系,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈;
所有点处理完之后栈中保存的点就是凸包了。
图示:
4,实现代码
5,应用:http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
实现代码:
2,凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。
3,Graham扫描法:
首先,找到所有点中最左边的(y坐标最小的),如果y坐标相同,找x坐标最小的.
以这个点为基准求所有点的极角(atan2(y-y0,x-x0)),并按照极角对这些点排序,前述基准点在最前面,设这些点为P[0]..P[n-1.
注:这样预处理后,保证p[0],p[1]和p[n-1]都是凸包上的点.
建立一个栈,初始时P[0]、P[1]、P[2]进栈,对于 P[3..n-1]的每个点,若栈顶的两个点与它不构成"向左转"的关系,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈;
所有点处理完之后栈中保存的点就是凸包了。
图示:
4,实现代码
#include <iostream> #include <cmath> using namespace std; /* PointSet[]:输入的点集 ch[]:输出的凸包上的点集,按照逆时针方向排列 n:PointSet中的点的数目 len:输出的凸包上的点的个数 */ struct Point { float x,y; }; //小于0,说明向量p0p1的极角大于p0p2的极角 float multiply(Point p1,Point p2,Point p0) { return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y)); } float dis(Point p1,Point p2) { return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))); } void Graham_scan(Point PointSet[],Point ch[],int n,int &len) { int i,j,k=0,top=2; Point tmp; //找到最下且偏左的那个点 for(i=1;i<n;i++) if ((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x))) k=i; //将这个点指定为PointSet[0] tmp=PointSet[0]; PointSet[0]=PointSet[k]; PointSet[k]=tmp; //按极角从小到大,距离偏短进行排序 for (i=1;i<n-1;i++) { k=i; for (j=i+1;j<n;j++) if( (multiply(PointSet[j],PointSet[k],PointSet[0])>0) ||((multiply(PointSet[j],PointSet[k],PointSet[0])==0) &&(dis(PointSet[0],PointSet[j])<dis(PointSet[0],PointSet[k]))) ) k=j;//k保存极角最小的那个点,或者相同距离原点最近 tmp=PointSet[i]; PointSet[i]=PointSet[k]; PointSet[k]=tmp; } //第三个点先入栈 ch[0]=PointSet[0]; ch[1]=PointSet[1]; ch[2]=PointSet[2]; //判断与其余所有点的关系 for (i=3;i<n;i++) { //不满足向左转的关系,栈顶元素出栈 while(multiply(PointSet[i],ch[top],ch[top-1])>=0) top--; //当前点与栈内所有点满足向左关系,因此入栈. ch[++top]=PointSet[i]; } len=top+1; } const int maxN=1000; Point PointSet[maxN]; Point ch[maxN]; int n; int len; int main() { int n=5; float x[]={0,3,4,2,1}; float y[]={0,0,0,3,1}; for(int i=0;i<n;i++) { PointSet[i].x=x[i]; PointSet[i].y=y[i]; } Graham_scan(PointSet,ch,n,len); for(int i=0;i<len;i++) cout<<ch[i].x<<" "<<ch[i].y<<endl; return 0; }
5,应用:http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
实现代码:
#include <iostream> #include <cmath> using namespace std; /* PointSet[]:输入的点集 ch[]:输出的凸包上的点集,按照逆时针方向排列 n:PointSet中的点的数目 len:输出的凸包上的点的个数 */ struct Point { float x,y; }; //小于0,说明向量p0p1的极角大于p0p2的极角 float multiply(Point p1,Point p2,Point p0) { return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y)); } float dis(Point p1,Point p2) { return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))); } void Graham_scan(Point PointSet[],Point ch[],int n,int &len) { int i,j,k=0,top=2; Point tmp; //找到最下且偏左的那个点 for(i=1;i<n;i++) if ((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x))) k=i; //将这个点指定为PointSet[0] tmp=PointSet[0]; PointSet[0]=PointSet[k]; PointSet[k]=tmp; //按极角从小到大,距离偏短进行排序 for (i=1;i<n-1;i++) { k=i; for (j=i+1;j<n;j++) if( (multiply(PointSet[j],PointSet[k],PointSet[0])>0) ||((multiply(PointSet[j],PointSet[k],PointSet[0])==0) &&(dis(PointSet[0],PointSet[j])<dis(PointSet[0],PointSet[k]))) ) k=j;//k保存极角最小的那个点,或者相同距离原点最近 tmp=PointSet[i]; PointSet[i]=PointSet[k]; PointSet[k]=tmp; } //第三个点先入栈 ch[0]=PointSet[0]; ch[1]=PointSet[1]; ch[2]=PointSet[2]; //判断与其余所有点的关系 for (i=3;i<n;i++) { //不满足向左转的关系,栈顶元素出栈 while(multiply(PointSet[i],ch[top],ch[top-1])>=0) top--; //当前点与栈内所有点满足向左关系,因此入栈. ch[++top]=PointSet[i]; } len=top+1; } const int maxN=1010; Point PointSet[maxN]; Point ch[maxN]; int n; int len; int main() { double ans=0; int d; cin>>n>>d; for(int i=0;i<n;i++) cin>>PointSet[i].x>>PointSet[i].y;//input the data; Graham_scan(PointSet,ch,n,len); for(int i=0;i<len;i++) ans+=dis(ch[i],ch[(i+1)%len]); ans+=2*d*acos(-1.0); //等价于圆形周长 cout<<(int)(ans+0.5)<<endl; //四舍五入 return 0; }
发表评论
-
为什么堆排比快排慢
2010-12-16 15:25 2966[节选]http://mindhacks.cn/200 ... -
使用map和hash_map的效率问题
2010-12-09 19:49 68421,选择map容器,是为了更快的从关键字查找到相关的对象。 与 ... -
斐波那契堆
2010-07-04 11:37 181, http://kmplayer.iteye.com/ad ... -
斐波那契堆
2010-07-04 11:36 1382学习的地方: http://en.wikipedia.org/ ... -
Sunday算法
2010-07-02 11:38 89011,Sunday算法是Daniel M.Sunday于1990 ... -
BM算法.
2010-07-02 10:53 76071,BM算法是Boyer-Moore算法的简称,由Boyer ... -
优先级队列
2010-06-17 23:15 11481,优先级队列是不同于 ... -
计数排序
2010-05-04 16:59 7401,计数排序是一个非基于比较的线性时间排序算法。 它对输入的数 ... -
归并排序
2010-05-04 16:47 8661,归并排序是建立在归并操作上的一种有效的排序算法。该算法是采 ... -
求大数阶层
2010-05-04 16:40 13081,思想类似于大数的加减乘法. 数组的每个元素维护一个4位数. ... -
基数排序
2010-05-03 16:45 856详细解释参考:http://en.wikipedia.org/ ... -
求两个数组的中位数
2010-05-02 12:08 40531,题目 有两个数组,均已经按升序排列好,编程序计算这两个数组 ... -
imba的bit向量
2010-04-22 17:30 8821,先给出一个模板. #include <iostr ... -
编写自己的malloc
2010-04-19 17:03 14651,如果一个程序大量调用malloc,程序的很多时间将会消耗在 ... -
快速排序
2010-04-01 13:50 6981,给出一个实现实例. #include <iost ... -
md5算法
2010-03-31 10:35 2621Message Digest Algorithm MD5( ... -
堆排序
2010-03-23 10:48 8551,"堆"定义 n个关 ... -
改进的线性筛法_寻找素数
2010-03-03 10:41 15611,实例代码: #include <iostream ... -
求有向图的强连通分量(scc):Tarjan算法
2010-02-28 15:41 142191,在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强 ... -
最近公共祖先LCA:Tarjan算法
2010-02-28 15:25 177761,并查集+dfs 对整个树进行深度优先遍历,并在遍历的过程中 ...
相关推荐
采用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扫描法实现凸包的绘制
一、数学问题 1.精度计算——大数阶乘.乘法.加法.减法 .任意进制转换.最大公约数、最小公倍数....计算几何.Graham扫描法寻找凸包 .数论.求解模线性方程 图论.Dijkstra算法求单源最短路径.数据结构 。
方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网。结果通过500至10000个点的测试,表明这种基于C-...
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扫描法): 旋转卡壳法: Image_BWLabel(Python): Two-Pass法: Image_DFT_IDFT(C++): Image_FFT_IFFT(C++): : Image_Hough(C++): : Image_Radon(C++): : Image_White_Balance(C++): 灰度世界算法...
Graham扫描法 水平序的引进,共线凸包的补丁 完美凸包算法 相关判定 两直线相交 两线段相交 点在任意多边形内的判定 点在凸多边形内的判定 经典问题 最小外接圆 近似O(n)的最小外接圆算法 点集直径 ...
凸包算法(Graham扫描法) Graham-Scan 辗转相除法求最大公约数 Greatest-Common-Divisor 堆排序 Heap-Sort ISAP算法 Improved-Shortest-Augmenting-Path(Naive) 插入排序 Insertion-Sort 字符串匹配(KMP) ...
12.Graham扫描法寻找凸包 数论: 1.x的二进制长度 2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7.判断一个数是否素数 ...
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 ...
该算法首先使用Canny算子提取叶片轮廓,然后使用基于平面扫描法的Graham算法构造叶片轮廓凸包,最后提取叶片最小外接矩形。仿真实验结果表明:在Flavia植物叶片数据库中进行测试,该算法优于旋转法、顶点链码法。
| GRAHAM 求凸包 O(N * LOGN) 34 | 判断线段相交 34 | 求多边形重心 34 | 三角形几个重要的点 34 | 平面最近点对 O(N * LOGN) 34 | LIUCTIC 的计算几何库 35 | 求平面上两点之间的距离 35 | (P1-P0)*(P2-P0)...