您好、欢迎来到现金彩票网!
当前位置:2019正版免费全年资料 > 凸包 >

凸包的发展历史急需越详细越好谢谢!!!!

发布时间:2019-06-26 20:35 来源:未知 编辑:admin

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部⒈对于一个集合D,D中任意有限个点的线性组合的全体称为D的凸包。 ⒉对于一个集合D,所有包含D的凸集之交称为D的凸包。 可以证明,上述两种定义是等价的 概念

  1 点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 2 一组平面上的点,求一个包含所有点的最小的凸多边形,这就是凸包问题了。这可以形象地想成这样:在地上放置一些不可移动的木桩,用一根绳子把他们尽量紧地圈起来,并且为凸边形,这就是凸包了。编辑本段平面凸包求法常见求法

  概念 凸包(Convex Hull)是一个计算几何(图形学)中的概念。用不严谨的话来讲,给定二维平面上的点集,凸包就是将最外层的点连接起来构成的凸多边型,它能包含点集中所有点的。严谨的定义和相关概念参见维基百科:凸包。 这个算法是由数学大师葛立恒(Graham)发明的,他曾经是美国数学学会(AMS)主席、AT&T首席科学家以及国际杂技师协会(IJA)主席。(太汗了,这位大牛还会玩杂技~) 问题 给定平面上的二维点集,求解其凸包。 过程 ⒈ 在所有点中选取y坐标最小的一点H,当作基点。如果存在多个点的y坐标都为最小值,则选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量H,p;与x轴的夹角进行排序,夹角由大至小进行顺时针扫描,反之则进行逆时针扫描。实现中无需求得夹角,只需根据向量的内积公式求出向量的模即可。以下图为例,基点为H,根据夹角由小至大排序后依次为H,K,C,D,L,F,G,E,I,B,A,J。下面进行逆时针扫描。 ⒉ 线段H,K;一定在凸包上,接着加入C。假设线段K,C;也在凸包上,因为就H,K,C三点而言,它们的凸包就是由此三点所组成。但是接下来加入D时会发现,线段K,D;才会在凸包上,所以将线段K,C;排除,C点不可能是凸包。 ⒊ 即当加入一点时,必须考虑到前面的线段是否会出现在凸包上。从基点开始,凸包上每条相临的线段的旋转方向应该一致,并与扫描的方向相反。如果发现新加的点使得新线段与上线段的旋转方向发生变化,则可判定上一点必然不在凸包上。实现时可用向量叉积进行判断,设新加入的点为pn + 1,上一点为pn,再上一点为pn - 1。顺时针扫描时,如果向量pn - 1,pn;与pn,pn + 1;的叉积为正(逆时针扫描判断是否为负),则将上一点删除。删除过程需要回溯,将之前所有叉积符号相反的点都删除,然后将新点加入凸包。 在上图中,加入K点时,由于线段H,K;相对于H,C;为顺时针旋转,所以C点不在凸包上,应该删除,保留K点。接着加入D点,由于线段K,D;相对H,K;为逆时针旋转,故D点保留。按照上述步骤进行扫描,直到点集中所有的点都遍例完成,即得到凸包。 复杂度 这个算法可以直接在原数据上进行运算,因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中,则可能在代码级别进行优化。由于在扫描凸包前要进行排序,因此时间复杂度至少为快速排序的O(nlgn)。后面的扫描过程复杂度为O(n),因此整个算法的复杂度为O(nlgn)。 ⒉1凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。 对于一个有三个或以上点的点集Q,过程如下: 计算点集最右边的点为凸包的顶点的起点,如上图的P3点。 Do For i = 0 To 总顶点数 计算有向向量P3-Pi If 其余顶点全部在有向向量P3-Pi的左侧或右侧,则Pi点为凸包的下一顶点 Pi点加入凸包列表 GoTo 1 End If Next Exit Do 1: Loop 此过程执行后,点按极角自动顺时针或逆时针排序,只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。

  ⒉2求凸包有很多方法,不过最适合OIer和ACMer的估计还是Grahams Scan这个方法了。它的大致方法是这样的:首先,找到所有点中最左边的(y坐标最小的),如果y坐标相同,找x坐标最小的;以这个点为基准求所有点的极角(atan2(y-y0,x-x0)),并按照极角对这些点排序,前述基准点在最前面,设这些点为P[0]..P[n-1];建立一个栈,初始时P[0]、P[1]、P[2]进栈,对于P[3..n-1]的每个点,若栈顶的两个点与它不构成“向左转”的关系,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈;所有点处理完之后栈中保存的点就是凸包了。 如何判断A、B、C构成的关系不是向左转呢?如果b-a与c-a的叉乘小于0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x。 上面的这个Graham的实现比我原来按照USACO里的课文写得简单多了,主要是它通过简单的预处理保证了P[0]、P[1]以及P[n-1]肯定是凸包里的点,这样就可以避免在凸包“绕回来”的时候繁杂的处理。

  先构造一个中心点,然后将它与各点连接起来,按斜率递增的方法,求出凸包上部;再按斜率递减的方法,求出凸包下部。

  从最左边的点开始,按斜率递增的方法,求出凸包上部;再按斜率递减的方法,求出凸包下部。水平法较中心法减少了斜率无限大的可能,减少了代码的复杂度。编辑本段代码例代码一

  (在编辑器中将_ (下划线+空格)替换成两个空格即可编译; 注意要去掉开通的双字节中文空格,蛋疼的百科。)

http://exlei.net/tubao/292.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有