11月10, 2018

了解凸包及Graham scan

Graham's scan是一种在时间复杂度为O(n log n)的平面中找到有限点集的凸包的方法。它以 Ronald Graham的名字命名,他在1972年发表了原始算法。该算法找到沿其边界排序的凸包的所有顶点。它使用堆栈有效地检测和去除边界中的凹陷。

问题描述:二位平面内,给定n个散乱的点,求一个最小凸多边形(凸包),使得n个点都不在凸多边形外。
问题的解决用到Graham算法:

算法步骤:

1.取y坐标最小的一点,作为p0,显然p0一定在凸包上。 alt

2.将p0作为坐标系原点,其他点按极角从小到大排序,从p1开始编号。

alt

3.从小到大遍历所有点:显然[p0, p1] 在凸包中

alt

4.连接p1, p2的时候需要判断:p0->p1 叉乘 p1->p2 是否大于0:

> 0    p1->p2p0->p1 夹角小于π,物理意义:p1->p2p0->p1的左边,满足凸多边形定义。
= 0    p1->p2p0->p1 共线,同向满足,相反不满足。
< 0    p1->p2p0->p1 夹角大于π,不满足。

alt

5.连接p2, p3 向量p2->p3在p1->p2左边,满足定义,当连接p3, p4的时候,发现不满足定义了,此时要放弃p3, 从p2开始回溯,找到第一个满足要求的点。

alt

6.以此类推,知道回到p0点。

alt

Graham scan 正确性:

令散点的数量为k,散点(p0 ~ pk – 1)已经按照极角排序。

    当k=3时,显然,p0->p1时凸包的一条边,且p2 极角小于p1, 那么p1->p2p0->p1的左侧,所以p1->p2保留。

    当k=n时,假设此时(p0 ~ pn – 1) 都按照Graham scan找出“最完美的凸包”

    当k=n+1时,如果pn – 1 -> pn 在 pn – 2 > pn – 1左边,如下图,如果舍弃pn,直接连接pn – 1 -> p0, 那么pn在多边形外,不满足要求。

alt

    证毕。

本文链接:https://www.opsdev.cn/post/convexhull.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。