一种形象的理解是:我们用一根麻绳绑住一个外面的钉子(点), 然后拉着麻绳绕所有钉子一圈,这个麻绳最后也构成了点集的凸包。
这就是卷包裹法(Gift Wrapping)的思路
卷包裹算法从一个必然在凸包上的点开始向着一个方向依次选择最外侧的点,当回到最初的点时,所选出的点集就是所要求的凸包。这里还有两个问题不是很清楚:
1.怎么确定一个肯定在凸包上的点?
这个问题很好解决,取一个最左边的也就是横坐标最小的点(或最下边的点,纵坐标最小的),如果有多个这样的点, 就取这些点里纵坐标(横坐标)最小的。
2.如何确定下一个点(即最外侧的点)?
需要利用向量的叉积来解决这个问题
比如现在我们卷包裹卷到J点我们要选取一个最外侧的点,当然比较红色的到角可以直接得到最外侧的点,不过不方便,我们可以考虑那个蓝色的到角,利用向量 我们可以比较哪个点"更外侧"。比如点K和点I,我们利用向量JK乘以向量JI得到一个数,这个数应该是负数,说明I比K更外侧。两个向量的比较具有传递性,所以我们可以像N个数里取最大的数一样取出最外侧的。
遍历所有点,每个点都和现有最外侧的点比较,得到新的最外侧的点。
至此两个问题都得以解决 我们可以写出满足一般要求的卷包裹算法了,不过还遗留有一个问题 就是处理共线的问题。有时候我们需要凸包边上的点也考虑到,有时候却需要去掉这些点,我们通常称在凸包顶点处的点为极点,如果我们只要求保留极点而去除在边上的点,我们只需在取外侧的点的时候,碰到共线的点取最远的,相反 如果我们要保留所有在边上的点我们只需要在共线的点中取最近的。这样整个卷包裹法终于完成了:
下面是卷包裹算法解poj 1113的AC代码:
关于POJ 1113请参看:
http://128kj.iteye.com/blog/1748635
import java.util.*;
class point implements Comparable {//平面上的一个点
double x;
double y;
public int compareTo(Object o) {//按y升序排列,y相同按x升序
point b=(point)o;
if(this.y>b.y) return 1;
else if(this.y==b.y ){
if(this.x>b.x) return 1;
else if(this.x==b.x) return 0;
else return -1;
}
else return -1;
}
}
public class Main{
point[] A;//已知的平面上的点集
boolean[] F;//F[i]标记A[i]是否已在凸包中
Queue< Integer> Q=new LinkedList< Integer>();//点集A的凸包,
int n;
int l;
public Main(){
}
//向量ca与ba的叉积
double cross(point c,point a,point b) {
return (c.x-a.x)*(a.y-b.y)-(c.y-a.y)*(a.x-b.x);
}
//求距离
public double distance(point p1, point p2) {
return (Math.sqrt((p1.x - p2.x) * (p1.x- p2.x) + (p1.y - p2.y)* (p1.y - p2.y)));
}
//显示A
public void print(){
for(int i=0;i< A.length;i++){
System.out.println("["+A[i].x+","+A[i].y+"] ");
}
}
public void go(){
Scanner in=new Scanner(System.in);
n=in.nextInt();
l=in.nextInt();
A=new point[n+1];
F=new boolean[n+1];
for(int i=1;i<=n;i++){
A[i]=new point();
A[i].x=in.nextDouble();
A[i].y=in.nextDouble();
}
Arrays.sort(A,1,A.length-1);//注意这个排序从1开始
//确定一个肯定在凸包上的点
F[1]=true;//注意这里将A[1]标记为放进凸包,并不真正放进
int last=1;
while(true){
int Minn=-1;
for(int i=1;i<=n;i++) if(!F[i]) {//找一个不在凸包上的点
Minn=i;
break;
}
if(Minn==-1) break;//找不到,结束
for(int i=1;i<=n;i++) //遍历所有点, 每个点都和现有最外侧的点比较,得到新的最外侧的点
if((cross(A[last],A[i],A[Minn])>0)|| (cross(A[last],A[i],A[Minn]) == 0) &&
(distance(A[last], A[i]) > distance(A[last], A[Minn])))
Minn=i;
if(F[Minn]) break;//找不到最外侧的点了
Q.offer(Minn);//最外侧的点进凸包
F[Minn]=true;//标记这点已放进凸包了
last=Minn;
}
double ans=Math.PI*2*l;//计算圆周长
last=1;
Q.offer(1);//最后将A[1]放进凸包
while(!Q.isEmpty())//计算圆周长+凸包周长
{
int tmp=Q.poll();
ans+=Math.sqrt((A[last].x-A[tmp].x)*(A[last].x-A[tmp].x)
+(A[last].y-A[tmp].y)*(A[last].y-A[tmp].y));
last=tmp;
}
System.out.println((int)(ans + 0.5));
}
public static void main(String args[]){
Main ma=new Main();
ma.go();
}
}
本文图片和文字参照:
http://www.cnblogs.com/Booble/archive/2011/02/28/1967179.html
源码:
- 大小: 6.6 KB
- 大小: 8.2 KB
分享到:
相关推荐
求解凸包问题:输入是平面上 n 个点的集合 Q,凸包问题是要输出一个 Q 的 凸包。其中,Q 的凸包是一个凸多边形 P,Q 中的点或者在 P 上或者在 P 中。 实现基于枚举方法的凸包求解算法 实现基于 Graham-Scan 的凸包...
NULL 博文链接:https://128kj.iteye.com/blog/1749213
北大POJ1113-Wall【凸包】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1748635
我个人用java写的关于凸包的JarvisMarch算法,也称gift wrapping算法。比较完美,算法的实现很简洁,只有加减乘除的基本运算,程序运行效率很高,计算10万个点的运行时间大概20秒左右。适当增加Point类中的屏幕范围...
计算几何求凸包的java代码,运行可用,可以鼠标任意点击去点,并绘制离散点的最大凸包。
哈工大算法实验一,凸包问题 1.基于枚举方法的凸包求解算法 2.实现基于Graham-Scan的凸包求解算法 3.实现基于分治思想的凸包求解算法 4.界面图,可以用鼠标随便点,然后用这些点求出凸包并在界面上画出凸包源代码和...
计算凸包常用的一种算法--graham算法。
graham求凸包算法 graham求凸包算法 graham求凸包算法 graham求凸包算法 graham求凸包算法 graham求凸包算法
Melkman凸包算法及Java实现,以及相关文档资料
凸包melkman算法cpp实现,通过poj1113题测试
作者对原算法的错误处进行了校正,可以作为大家学习参考使用,如果在公共场合使用本资源和算法更正的内容请标明出处,并及时与作者取的联系。未经允许不得以任何目的在公共场合(包括论文)使用或模仿本算法。版权归...
NULL 博文链接:https://128kj.iteye.com/blog/1748442
c++实现的GraHam算法,解决凸包问题
凸包卡壳算法求点集内距离最远的两点之间的距离,C代码+注解
实现凸包实现,采用MATLAB编写代码,用于凸包算法的快速实现。
poj1113 melkman算法求凸包, 使用STL
自己写的解决凸包问题的代码,还具备界面。
两种凸包算法 算法导论的详细实现 C++ VS2008