- 浏览: 303500 次
- 性别:
- 来自: 天津
文章分类
最新评论
-
suxiaojack:
15题,就是拿杨辉三角填充空格,答案应该是C(38,19)吧? ...
Project Euler解题汇总 013 ~ 022 -
songhaikang:
这篇文章挺好的,跟着你的步骤很快就可以入门了。非常感谢。
[转贴]Derby入门 —— (1) -
Eastsun:
呵呵,我没有Android的机器,所以兴趣不大
使用Java写的GVmaker虚拟机(开源) -
crapricorn:
那个版本的用不了虚拟键盘啊 呵呵 我们的手机没有实体键盘呀 所 ...
使用Java写的GVmaker虚拟机(开源) -
Eastsun:
crapricorn 写道希望sun侠能做出个android平 ...
使用Java写的GVmaker虚拟机(开源)
前言
:因为前几天做了一个有关凸包的题,并答应crackerwang写个blog解释一下我的算法.因为我比较懒的原因,一直拖到现在才写.预计一共有两篇,第一篇介绍求二维点集凸包的O(N*logN)时间复杂度的算法.第二篇介绍求凸包直径的O(N)时间复杂度的算法.
下面首先给出http://acm.tju.edu.cn/toj/showp2847.html
该题的C++代码,本文将使用Java
代码来描述.
- /**
- * TJU 2847 的C++解法
- * Written By Eastsun
- */
- #include<stdio.h>
- #include<math.h>
- #include<algorithm>
- #include<functional>
- #define S(arr,a,b,c) ((arr[b].x-arr[a].x)*(arr[c].y-arr[a].y)-(arr[c].x-arr[a].x)*(arr[b].y-arr[a].y))
- #define J(arr,a,b,c,d) ((arr[b].x-arr[a].x)*(arr[d].y-arr[c].y)-(arr[d].x-arr[c].x)*(arr[b].y-arr[a].y))
- #define Q(x) ((x)*(x))
- #define D(arr,a,b) (Q(arr[a].x-arr[b].x)+Q(arr[a].y-arr[b].y))
- using namespace std;
- struct Point{
- double x,y;
- };
- struct myCmp: public binary_function<Point,Point, bool >{
- bool operator()( const Point& p1, const Point& p2) const {
- if (p1.x==p2.x) return p1.y<=p2.y;
- else return p1.x<p2.x;
- }
- };
- int main(){
- int n;
- while (scanf( "%d" ,&n),n){
- Point *ps = new Point[n];
- for ( int i=0;i<n;i++) scanf( "%lf%lf" ,&ps[i].x,&ps[i].y);
- sort(ps,ps+n,myCmp());
- int *v = new int [2*n];
- int p,q;
- p =q =n;
- for ( int i=0;i<n;i++){
- v[p] =v[q] =i;
- while (p-n>=2&&S(ps,v[p],v[p-1],v[p-2])>=0){v[p-1] =v[p]; p--;}
- while (n-q>=2&&S(ps,v[q+2],v[q+1],v[q])>=0){v[q+1] =v[q]; q++;}
- p++;
- q--;
- }
- int len =p -q -2;
- Point *pps = new Point[len+2];
- for ( int i=q+1;i<p;i++) pps[i-q] =ps[v[i]];
- pps[0] =pps[len];
- int i=0,j=1;
- while (J(pps,i,i+1,j,j+1)>0) j++;
- double max =0;
- while (i<=len){
- double det =J(pps,i,i+1,j,j+1);
- if (det<0) i++;
- else if (det>0) j =(j+1>len?j+1-len:j+1);
- else {
- i++;
- continue ;
- }
- double tmp =D(pps,i,j);
- if (tmp>max) max =tmp;
- }
- delete [] ps;
- delete [] pps;
- delete [] v;
- printf( "%.2lf\n" ,sqrt(max));
- }
- return 0;
- }
一:凸包的定义及其应用
对于二维点集,其凸包(convex hull)是指包含所有点的最小的凸多边形.直观上看,如果用一条橡皮筋将所有的点圈住,当橡皮筋拉紧后的形状就是这些点的凸包.
下面就是凸包的示意图:
那么,我们为什么需要凸包这个概念呢?它又能解决什么问题?
首先,凸包上的点相对原有的点集,我们可以想象,其数量将大大减少.研究表明,对于二维情形,凸包顶点数m(k) =O(n^1/3).更一般的,对于k维球体中均匀分布的n个点,其凸包顶点数m(k) =O(n^(k-1)/(k+1)),可见凸包可大大降低平均意义下的时空复杂度.
另一方面,凸包相对原有点集增加了一个"序",原来是一个杂乱无章的点集,而现在是一个性质优美的凸多边形,研究起来方便很多.
关于其应用,这里我们只针对TJU2847来说,原题是求一个点集中任意两点的距离的最大值.显然,如果我们直接考虑这个点集中任意两点的距离,时间复杂度是O(N^2),下面我们可以看到,当求出其凸包后,我们可以在O(k)时间内求出这个值(这里的k是指凸包顶点个数k<=N).再加上构造凸包的时间复杂度O(N*logN),我们在O(N*logN)时间复杂度内解决了这个问题.
二:构造凸包的算法
二维点集构造凸包的算法有:卷包裹法(Gift-Wrapping),Graham-Scan扫描法以及分治算法,增量算法等等.这里我采用的是Graham-Scan算法的一种变形--x-y排序.(至于原本的极角排序的Graham-Scan算法,有兴趣的可以参阅《Introduction to Algorithms》第VII章的Computational Geometry一节,里面有详细的说明及正确性证明):
首先将给定点集对x的值进行排序,x值相同的按y的值排序.简单来说就是从左到右,从下到上排序.
排序后,记这些点为ps[0,1,..,k],显然点列的第一个点与最后一个点都在凸包上(想一想那个橡皮筋),然后我们从第一点开始到最后一个点进行如下处理:
构造一个堆栈(数组)stack[],stack[0] =ps[0],然后维持栈中点都是按右手系旋转(或者说从stack[0]到stack[p],所有的点都是按逆时针排列),对于每一个新增加的点,都首先检查栈顶的两个点与其是不是保持右手系,如果是,把这个点加入栈;否则,将栈顶点去掉,继续检查...一直到符合要求为止.
这样处理后的结果是:stack[]中得到一条连接ps[0]与ps[k]的,并且维持逆时针顺转的链.这个链就是我们要求的凸包的下半部分.用伪代码来描叙就是:
- //ps中保存了已经排好序的点
- Point[] stack = new Point[ps.length];
- int index = 0 , p = 0 ;
- while (index
- stack[p] =ps[index++];
- while (p>= 2 && stack[p- 2 ],stack[p- 1 ],stack[p] 不是右手系){
- stack[p- 1 ] =stack[p];
- p --;
- }
- p ++;
- }
显然,我们再从ps[k]到ps[0]做类似的处理就可以得到凸包的上半部分.当然,事实上我们可以把这两个工作一起做了:维持一个双头栈,使其头部的三个点为右手系,其尾部的三个点为左手系.这样经过一次扫描就可以得到整个凸包.伪代码如下:
- //ps中保存了已经排好序的点
- Point[] stack = new Point[ 2 *ps.length];
- int index = 0 , head =ps.length,tail =ps.length;
- while (index
- stack[head] =stack[tail] =ps[index++];
- while (head-ps.length>= 2 && stack[head- 2 ],stack[head- 1 ],stack[head] 不是右手系){
- stack[head- 1 ] =stack[head];
- head --;
- }
- while (ps.length-tail>= 2 && stack[tail+ 2 ],stack[tail+ 1 ],stack[tail] 不是左手系){
- stack[tail+ 1 ] =stack[tail];
- tail ++;
- }
- head ++;
- tail --;
- }
可以看出,整个算法并不复杂,或者可以说很优美.哦,等等,伪代码里面还有个判断"左手系","右手系"是怎么来的?这就涉及到一个数学概念:叉积
三:叉积
叉积,又叫外积,向量积.这里我不对叉积做太深入的探讨,只做一些概念性的描叙(且没有考虑数学上的准确性,只是为了解决问题方便),有兴趣的可以找本大学的<解析几何>之类的数学书看看.
定义:对于二维平面的两个向量a =[xa,ya],b =[xb,yb],其叉积 a×b =xa*yb -xb*ya (其实叉积的定义是在三维空间中的..)
另一方面,对于点X1 =[x1,y1],X2 =[x2,y2],对应的向量 X1X2 =[x2-x1,y2-y1]
性质:
对于平面上的三个点A,B,C所组成的三角形ABC的面积是向量AB与AC叉积的绝对值的一半,即 2*S(A,B,C) =|AB×AC|,并且当A,B,C三点按逆时间顺转时,AB×CD为正;当A,B,C三点按顺时间顺转时,AB×AC为负;A,B,C三点共线时,其叉积为0.
四:具体代码
有了上面的知识,下面给出具体的求凸包的Java代码.
首先给出用于表示Point的类:
- package convex;
- public class Point implements Comparable<Point>{
- public double x,y;
- public static double distanceSq(Point p1,Point p2){
- return (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y);
- }
- public Point(){
- this ( 0.0 , 0.0 );
- }
- public Point( double x, double y){
- this .x =x;
- this .y =y;
- }
- /**
- * 实现Comparable的compareTo方法,将Point按从左到右,从下到上排序
- */
- public int compareTo(Point p){
- if (x ==p.x) return y==p.y? 0 :(y>p.y? 1 :- 1 );
- else return x>p.x? 1 :- 1 ;
- }
- }
- package convex;
- import static java.util.Arrays.sort;
- /**
- * 用于求点集凸包以及求凸包直径的算法类
- */
- public class Algorithm{
- //避免生成该类实例
- private Algorithm(){}
- /**
- * 构造Point数组ps中从fromIndex到toIndex的Point的凸包,时间复杂度O(N*logN)
- * 注意: 该方法可能改变ps数组中从fromIndex到toIndex元素的顺序
- * 前置条件: 一个任意的二维点集,不同点的个数>=2
- *@param ps 保存二维点集的Point数组
- *@param fromIndex 点集在数组中的起始位置
- *@param toIndex 点集在数组中的结束位置
- *@param convex 用来保存凸多边形的顶点的Point数组,其顶点将按逆时针排列
- *@param offset 保存数据在convex数组中的起始位置
- *@return length 凸多边形的顶点数目
- */
- public static int getPointsConvexClosure(Point[] ps, int fromIndex, int toIndex,Point[] convex, int offset){
- sort(ps,fromIndex,toIndex);
- int len =toIndex -fromIndex;
- Point[] tmp = new Point[ 2 *len];
- int up =len, down =len;
- for ( int index =fromIndex;index
- tmp[up] =tmp[down] =ps[index];
- while (len-up>= 2 &&multiply(tmp[up+ 2 ],tmp[up+ 1 ],tmp[up])>= 0 ){
- tmp[up+ 1 ] =tmp[up];
- up++;
- }
- while (down-len>= 2 &&multiply(tmp[down- 2 ],tmp[down- 1 ],tmp[down])<= 0 ){
- tmp[down- 1 ] =tmp[down];
- down--;
- }
- up --;
- down ++;
- }
- System.arraycopy(tmp,up+ 1 ,convex,offset,down-up- 2 );
- return down-up- 2 ;
- }
- /**
* 计算向量ab与ac的叉积
*/
private static double multiply(Point a,Point b,Point c){
return multiply(a,b,a,c);
}
/**
* 计算向量ab与cd的叉积
*/
private static double multiply(Point a,Point b,Point c,Point d){
return (b.x-a.x)*(d.y-c.y)-(d.x-c.x)*(b.y-a.y);
} - }
- convex.rar (3 KB)
- 描述: 本文中使用的Java代码,并包含TJU2847的 Java代码
- 下载次数: 65
评论
这次你真的不用写了.
非常谢谢.以后在请教你其他问题
你这个构造凸包的方法不错比那个算及角的要减少精度误差.
算直径的还不是很明白.
凸包那个算法还好.
不过还是有点小小的问题.
这个地方while(down-len>=2&&multiply(tmp[down-2],tmp[down-1],tmp[down])<=0){
tmp[down-1] =tmp[down];
down--;
}
改成while(down-len>=2&&multiply(tmp[down-2],tmp[down-1],tmp[down])<0)
求周长会不会有影响?
上次在做一个题目的时候发现加等号错不加就对.一直没有找到这个特殊的数据
你说“终于明白了”。
我还以为我可以不用写第二篇了。
不过你还是先自己google一下吧,我现在不在学校不方便写。
你的RMQ是在哪本书上看到的..
难道是传说中的算法导论??
某年月日,某人问我:你可知道 RMQ 问题?
我说:不曾听过这个名字。
某人于是描述了一遍 RMQ 问题,并说:似乎有一个算法,可以做到预处理时间 O(n),查询时间 O(1)。
我想了一回,便说:那定然是个很精巧的算法,我不能及。
某人说:请替我查访一下罢。
我说:好,我便查访一下罢。
于是我拜请 google 大神,照见一切以 RMQ 为名的先贤足迹,于 15 分钟后寻得 R.E.Tarjan、M.A.Bender 等先知留下的文献卷轴。于是 RMQ-LCA 问题的一切秘奥,均展现在我们的眼前。
于是某人说:赞美政委大能!算法的光辉必将照亮一切黑暗前路。
我说:善。
你的RMQ是在哪本书上看到的..
难道是传说中的算法导论??
http://acm.pku.edu.cn/JudgeOnline/problem?id=2823
这道题用 RMQ 应该是违规的。从题意来看,任意时刻你应该只能访问其中 k 个元素。而且事实上,这题用 RMQ 也是牛刀割鸡了。
但是我在做那个题目的时候是想构造一个最小外接圆,然后在求上面所有点的两两距离.最后因为没有看明白书上的dephi代码而做罢了..
看来eastsun大哥对算法和数据结构的功底不在一般计算机学生之下了..对你的佩服已经由如滔滔...(将来也要和你一样,嘿嘿)
我再问个典型算法的问题:RMQ-LCA,你会吗?这个好像是个很典型的算法,但是在网上却找不到很好的答案...你要是会就稍微在底下给我留言一下...(当然要是再写个BLOG就更加好了..嘿嘿)
具体的问题你可以参照这个:http://acm.pku.edu.cn/JudgeOnline/problem?id=2823
我用优先队列过是能过,但是效率就....
直接看 The LCA Problem Revisted 这篇论文好了,可以直接下载,很容易懂。
但是我在做那个题目的时候是想构造一个最小外接圆,然后在求上面所有点的两两距离.最后因为没有看明白书上的dephi代码而做罢了..
看来eastsun大哥对算法和数据结构的功底不在一般计算机学生之下了..对你的佩服已经由如滔滔...(将来也要和你一样,嘿嘿)
我再问个典型算法的问题:RMQ-LCA,你会吗?这个好像是个很典型的算法,但是在网上却找不到很好的答案...你要是会就稍微在底下给我留言一下...(当然要是再写个BLOG就更加好了..嘿嘿)
具体的问题你可以参照这个:http://acm.pku.edu.cn/JudgeOnline/problem?id=2823
我用优先队列过是能过,但是效率就....
你终于弄上来了...
学习一下先
发表评论
-
使用基于邻接表的Dijkstra算法求解Project Euler问题
2008-10-04 21:56 3454Project Euler中的几个问题 首先,来看一看P ... -
《程序员》2007第十期算法擂台之JAVA解法
2007-10-15 23:46 2681题目: 引用 人和计算机做猜数游戏.人默想一个四位数,由计算机 ... -
《程序员》2007第九期之算法擂台
2007-09-16 00:42 3147原题: 在8*8的棋盘上分布着n个骑士,他们想约在某一格中聚会 ... -
《程序员》2007第八期之算法擂台
2007-08-19 19:55 3254题目描述(手头没书,不知道有没有记错):有v个在一条直线上的村 ... -
一个关于字符串操作的算法题
2007-08-01 19:46 2729最近在网上看到一道关于字符串操作的算法题,不过原题的表述以及给 ... -
程序员2007年3月刊上的一道算法题
2007-05-05 23:16 8484晚上无聊的时 ... -
几个经典的博弈问题
2007-03-26 18:34 5549有一种很有意思的游戏,就是有物体若干堆,可以是火柴棍或是围棋子 ... -
求1~N中1出现的次数的递归算法
2007-03-14 17:02 4111在网上看到的一个算法题,据说是某个大公司的面试 ... -
利用正则式计算表达式的值
2007-02-26 14:00 3153RT,最近又看了下JAVA的正则式,解决了之前对JAVA中正则 ...
相关推荐
一个很好的电子书文档,学习时偶然发现的 共同努力~~
改进的凸包算法,对研究新的图像识别算法有帮助。
VC下输入平面点集点的个数,随机生成这些点,求凸包及其直径。Debug下坐标点显示,openGL坐标图显示。不想用OpenGL可以注释掉相应代码,只用Debug显示点的坐标。
实现点集凸包的算法,把众多随机分布的点用一条折线以最小的长度使其全部包括其中
实现了一个2维点集的凸包算法,其中用到快速排序。
点集的最优实时算法, 其时间复杂度为它同样适用于多边形并具有相同的时间复杂度它还便 于控制结果凸包的方向, 只需调整初始三角形的方向即可, 算法其它部分无需修改算法具有高效、稳 定等特点, 从而在结合崔国华等的...
本文参考自算法导论>>章节33.3,利用Graham算法寻找二位平面散点集的凸包,利用OpenGL将计算的结果绘制出来.算法主要利用向量的叉积判断点和线段的位置关系,详见 向量叉积,然后从左下角点按逆时针方向寻找最边缘的线段...
26 Qhull(二维三维三角分解、泰森图)凸包工具箱 2019版 27 jplv7 28 MatlabFns 29 张量工具箱Tensor Toolbox 30 海洋要素计算工具箱seawater 31 地图工具箱m_map 32 othercolor配色工具包 33 Matlab数学建模工具箱 ...
二维凸包的寻找是计算几何学的经典问题之一。...给定平面上的一个点集,找出一个最小点集顺次连结形成一个凸多边形,使得点集中的点皆在此多边形内或此多边形上,这个凸多边形就是给定点集的二维凸包。
针对二维点集,提出了一种新的求解信息完整和不完整点集对称轴的方法。首先根据凸壳算法求出点集的凸壳,对于信息完整点集,点集的对称轴必是凸壳的对称轴,因此可以借助求解凸壳的对称轴来求解点集的对称轴;对于...
三维点集配准 迭代最近点法 截尾误差 可用于图像配准、立体匹配
三维点集的自动表面重构算法 三维 三维点集的自动表面重构算法点集的自动表面重构算法
ConvexHull2D 一个周末项目,使用 C++ 和标准库实现各种算法以查找一组 2D 点的凸包。 包括 Graham 的扫描、礼品包装算法、单调链算法和 QuickHull。 为清楚起见,代码没有考虑重复或共线的点。
基于SVD算法求解三维点集匹配的Matlab代码(带详细注释)
关于3d乱序点的生成,三维点集Voronoi图的算法实现
此函数计算单位圆内的点集的单个 Voronoi 单元面积。 输入: x : M x 1 x 坐标数组y : M x 1 y 坐标数组toggleplot : 1 打开数字,0 关闭数字; 输出: CellArea :M x 1 阵列的 Voronoi 单元区域以单位圆为界
对UCI数据集之一进行PCA特征抽取实验,给出在二维PCA特征空间的数据散点图。
CGAL模型凸包计算,利用CGAL计算几何算法库,解决了模型凸包运算问题。资源包含完整代码和详细说明文档。
根据已知顶点集合,求覆盖所有点的凸包,返回构成该凸包的所有顶点的集合,用的是扫描法,该代码针对二维空间下的点集,用C#实现。
用C#编写的图形界面演示凸包。 private void Form1_MouseClick(object sender, MouseEventArgs e) { g.FillEllipse(bPoint, e.X, e.Y, 5, 5); list.Add(e.Location); } /// /// 凸包算法 /// /// ...