- 浏览: 508807 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
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 3019[节选]http://mindhacks.cn/200 ... -
使用map和hash_map的效率问题
2010-12-09 19:49 68911,选择map容器,是为了更快的从关键字查找到相关的对象。 与 ... -
斐波那契堆
2010-07-04 11:37 181, http://kmplayer.iteye.com/ad ... -
斐波那契堆
2010-07-04 11:36 1423学习的地方: http://en.wikipedia.org/ ... -
Sunday算法
2010-07-02 11:38 89831,Sunday算法是Daniel M.Sunday于1990 ... -
BM算法.
2010-07-02 10:53 77061,BM算法是Boyer-Moore算法的简称,由Boyer ... -
优先级队列
2010-06-17 23:15 11941,优先级队列是不同于 ... -
计数排序
2010-05-04 16:59 7831,计数排序是一个非基于比较的线性时间排序算法。 它对输入的数 ... -
归并排序
2010-05-04 16:47 9021,归并排序是建立在归并操作上的一种有效的排序算法。该算法是采 ... -
求大数阶层
2010-05-04 16:40 13421,思想类似于大数的加减乘法. 数组的每个元素维护一个4位数. ... -
基数排序
2010-05-03 16:45 889详细解释参考:http://en.wikipedia.org/ ... -
求两个数组的中位数
2010-05-02 12:08 41061,题目 有两个数组,均已经按升序排列好,编程序计算这两个数组 ... -
imba的bit向量
2010-04-22 17:30 9321,先给出一个模板. #include <iostr ... -
编写自己的malloc
2010-04-19 17:03 15101,如果一个程序大量调用malloc,程序的很多时间将会消耗在 ... -
快速排序
2010-04-01 13:50 7371,给出一个实现实例. #include <iost ... -
md5算法
2010-03-31 10:35 2666Message Digest Algorithm MD5( ... -
堆排序
2010-03-23 10:48 8911,"堆"定义 n个关 ... -
改进的线性筛法_寻找素数
2010-03-03 10:41 16121,实例代码: #include <iostream ... -
求有向图的强连通分量(scc):Tarjan算法
2010-02-28 15:41 143071,在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强 ... -
最近公共祖先LCA:Tarjan算法
2010-02-28 15:25 178401,并查集+dfs 对整个树进行深度优先遍历,并在遍历的过程中 ...
相关推荐
采用Graham扫描法,实现提取凸包最小边界JS代码实现。(代码中点坐标采用平面坐标,如要在三维贴地展示,可转换为经纬度坐标)
本篇文章将详细探讨“学习凸包(四):Graham扫描法”,这是一种在二维空间中找到一组点的凸包的有效算法。 Graham扫描法由Ronald Graham于1972年提出,其基本思想是首先找到点集中一个最低的点,然后按照顺时针或...
在这个项目中,我们将探讨两种解决凸包问题的方法:Graham扫描法和分治策略。 1. **Graham扫描法**: - **基本原理**:Graham扫描法是一种基于极角排序的算法,首先找到一个最低点,然后按顺时针或逆时针顺序对...
解决凸包问题有多种算法,其中两种常见的方法是Jarvis步进法(Jarvis March)和Graham扫描法(Graham Scan)。 **Jarvis步进法**,又称为包裹法,其基本思想是从点集中选取一个必定在凸包上的点作为起点,然后通过...
首先,凸包的计算通常采用两种经典算法:Graham扫描法和Jarvis步进法。这里我们关注Graham扫描法,其时间复杂度为O(n log n),比Jarvis步进法(O(nh))更适用于点集较大且高度较小的情况。Graham扫描法的基本思路是...
Graham 扫描法是求解二维凸包的一种经典方法,由 Ronald Graham 在 1972 年提出。以下是该算法的主要步骤: 1. **找到最低点**:首先,我们需要找到点集中角度最小的点,即最左下角的点。这个点将成为凸包的起始点...
这个算法以电脑科学家Ronald Graham命名,其核心思想是找到散点集中最低的点作为起始点,然后通过旋转扫描线来确定凸包的边界点。具体步骤如下: 1. 找到散点集中的最低点,作为凸包的第一个点。 2. 对其余点按与...
凸包算法有多种实现方法,其中最著名的是Graham扫描法、Jarvis步进法和Andrew的扫地机算法。Graham扫描法首先找到所有点中的最低点,然后按照角度排序其余点,接着从最低点开始扫描,剔除那些在当前边与前一条边形成...
Graham扫描法是一种经典的求解凸包的算法,它首先找到所有点中的最低点,然后按照点相对于最低点的顺时针或逆时针顺序排序,最后通过不断去除内凹边界的点,直到所有剩余的点都在凸包上。以下是Graham扫描法的基本...
Graham算法的基本思想是先找到一个点,使得以此点为基准,其余点按逆时针或顺时针方向排序,然后通过一系列的扫描线操作逐步构建出凸包。以下是Graham算法的详细步骤: 1. **选择起点**:首先,从给定点集中选择一...
### 分治法解决凸包问题(用C语言递归调用实现) #### 一、引言 本篇文章将深入探讨如何使用分治策略来解决计算几何中的一个经典...此外,还可以考虑使用其他算法如Graham扫描法、Jarvis步进法等,以进一步优化性能。
例如,使用Graham扫描法的步骤可能如下: 1. 找到最低点,将其设为初始顶点。 2. 将其余点按相对于最低点的角度排序,角度从小到大。 3. 初始化一个空栈,将最低点压入栈。 4. 遍历排序后的点集,对于每个点,如果...
- 稳定性:某些算法如Graham扫描法是稳定的,即输入点的微小变化不会导致输出凸包的大幅度改变,这对于一些应用至关重要。 - 实现细节:C语言实现需要注意内存管理和计算效率,比如避免不必要的数据拷贝,使用指针...
4. 凸包构建:核心算法的实现,可能是Graham扫描或Andrew's反向扫描。 5. 鼠标事件处理:允许用户通过鼠标选择点,更新输入的点集。 6. 可视化:显示点集及计算出的凸包,可能是利用Java的Swing或JavaFX库。 代码中...
总结来说,"DEM两种凸包算法程序 C# .NET"是一个专注于C#环境下的数字高程模型处理项目,涵盖了Graham扫描法和Jarvis步进法两种凸包算法的实现。这些算法在地理信息处理、地图渲染、3D建模等领域有着广泛的应用,而...
在本实验中,我们将探讨三种解决凸包问题的方法:枚举法、Graham-Scan算法以及分治策略。下面将对这三种方法进行详细介绍。 首先,枚举法是最直观的一种解决方法。对于给定的一组点,我们可以尝试所有可能的点顺序...
描述中提到的"Gramham法"是一种常见的求解凸包的方法,也称为Graham扫描算法。该算法的基本思想是首先找到所有点中最低的三个点,然后按照逆时针或顺时针方向排序其余的点。接着,从这三个点开始,通过逐一检查新...
常见的有Graham扫描法、 Jarvis March( gift wrapping)法、Andrew算法等。这些算法都以相对简单的方式找到给定点集的凸包。以Graham扫描法为例,步骤包括: 1. 找到点集中最低的点,作为起始点。 2. 将其余点按照...
// 使用Graham扫描法计算凸包 Stack<Point> hullStack = new Stack(); hullStack.Push(points[0]); hullStack.Push(points[1]); for (int i = 2; i ; i++) { while (hullStack.Count >= 2 && ...