凸包 — Graham Scan算法分析与实现(C++)

凸包:点集Q的凸包(convec hull)是一个最小的凸多边形P,满足Q中的所有点或者在P的边界上,或者在P的内部。

例如:

convex_1

点集Q={p0, p1, …,p12}及其以灰色显示的凸包CH(Q)

这里介绍一种求凸包所包含点集的方法—Graham Scan。

这里在《算法导论》第33章计算几何学的第三节“寻找凸包”讲的很详细,还是以上图为例,看看凸包的建造过程:

convex_2

步骤1:如图(a),以y轴最低点为基点,找到基点p0。

步骤2:如图(a),以基点p0为一个坐标系的远点,求各点与基点p0的极角,并一次从小到大排序

步骤3:如图(b),按照顺序,每个点都要判断与其前面亮点构成的两条线段转向问题(左转还是右转?用叉积),这个具体看后面伪代码。

步骤4:依次下去,知道所有的点结束,就完成的凸包的寻找。

完整的图见《算法导论》P586~P587面。

这是《算法导论》上的伪代码:

GRAHAM-SCAN(Q)
 1  let p0 be the point in Q with the minimum y-coordinate,
             or the leftmost such point in case of a tie
 2  let 〈p1, p2, ..., pm〉 be the remaining points in Q,
             sorted by polar angle in counterclockwise order around p0
             (if more than one point has the same angle, remove all but
             the one that is farthest from p0)
 3  PUSH(p0, S)
 4  PUSH(p1, S)
 5  PUSH(p2, S)
 6  for i ← 3 to m
 7       do while the angle formed by points NEXT-TO-TOP(S), TOP(S),
                     and pi makes a nonleft turn
 8              do POP(S)
 9          PUSH(pi, S)
10  return S

可以看到步骤3,在伪代码中用Q保存凸包点集,每次按顺序从输入的点集P中取出一点P[i],与Q中最上面两点Q[top], Q[top-1]构成两条线段,若左转,则继续;否则将弹出栈顶的点Q[top],并再在栈中取一点Q[top-2],然后将P[i], Q[top-1], Q[top-2]继续比较,直至是左转~~~不好理解吧?还是看《算法导论》书上那图吧,神马讲解都是浮云,有图有真相才是王道。

理解后,看看这道题吧:

POJ 1113 Wall:http://poj.org/problem?id=1113

经典的凸包问题,这里就不做分析了,具体分析及代码在:http://www.wutianqi.com/?p=2613

另外,在学习凸包的过程中,在网上搜集到了两篇讲解的非常好的文章:

1.http://www.cnblogs.com/Booble/archive/2011/02/28/1967179.html

2.http://www.cnblogs.com/devymex/archive/2010/08/09/1795392.html

Tanky Woo 标签:

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《凸包 — Graham Scan算法分析与实现(C++)》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注