浏览量:256

8.3. Graham扫描算法

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

8.3. Graham扫描算法

Graham扫描算法会先将点按照极角的大小顺序排列,接着按顺序遍历每个点,通过夹角的大小判断哪些点在凸包上,算法的伪码如下所示:

求给定二维点集\(S=\{{{p}_{0}},{{p}_{1}},...,{{p}_{n-1}}\}\)的凸包
1.    求出最左下角的点,即\(X\)分量的值最小点,若\(X\)分量值最小的点有多个,取\(Y\)分量最小的点,设为\({{p}_{0}}\);
2.    剩下的点集,根据极角大小,逆时针排序,得到\(\{{{p}_{1}},...,{{p}_{m-1}}\}\);
3.    令栈\(Stack\)为空,用\(Stack[i]\)表示栈中第\(i+1\)个元素,用\(k\)表示栈中的元素个数;若栈中有\(k\)个元素,则\(Stack[k-1]\)即为栈顶元素;每一次\(\text{PUSH}\)操作,栈元素个数\(k\)加1;每次\(\text{POP}\)操作,栈元素个数\(k\)减1;
4.    \(\operatorname{PUSH}(Stack,{{p}_{0}})\);
5.    \(\operatorname{PUSH}(Stack,{{p}_{1}})\);
6.    for(\(i=2\) ; \(i\prec m\) ; \(i=i+1\))
7.           while (\(k\ge 2\) && 由\(Stack[k-2]\),\(Stack[k-1]\)\({{p}_{i}}\)的夹角\(\theta \ge 180\))
8.                  \(POP(Stack)\);
9.           end while;
10.   end for;
11.   if \(k\prec 3\), then
12.          点集无法生成一个凸包;
13.   else
14.          栈\(Stack\)中的\(k\)个元素,就是凸包的顶点;
15.   end if;

2015-3-24 10-29-01

图8.9 Graham扫描算法过程

以如图8.9(a)所示为例,给定一个点集,\(\{{{p}_{0}},\cdots ,{{p}_{8}}\}\)。第1步,选择最左下角的点\({{p}_{0}}\),若\(X\)分量值最小的点有多个,取\(Y\)分量最小的点,特别注意,在实际实现中,可能存在多个相同的\({{p}_{0}}\)点,必需把它们排除,保证点\({{p}_{0}}\)是唯一的,否则在第2步中的排序会造成错误。第2步,如图(b)所示,对\(\{{{p}_{0}},\cdots ,{{p}_{8}}\}\)按照极角从小到大进行排序,若极角相同,则根据与点\({{p}_{0}}\)的距离从近到远排序。第3~5步,如图(c)所示,把\({{p}_{0}}\)\({{p}_{1}}\)两个点压入栈中。逆时针方向处理每个顶点,第6~10步,如图(d)~(i),若\(k\ge 2\)且由\(Stack[k-2]\),\(Stack[k-1]\)\({{p}_{i}}\)的夹角大于等式180度,则把栈顶元素出栈,否则把新点\({{p}_{i}}\)压入栈。最终得到的凸包如图(k)所示,点\({{p}_{7}}\)在线段\(\overline{{{p}_{6}}{{p}_{8}}}\)上,是否把它作为凸包的顶点,可以根据具体的问题再作决定,上面提供的算法伪码,不允许把点\({{p}_{7}}\)作为凸包的顶点。

对于对极点的排序,有多种算法实现,比如冒泡排序,快速排序,堆排序等,各种排序的性能对比,如表8.3的总结。若采用冒泡排序,则Graham扫描算法的复杂度将达到\(O({{n}^{2}})\),采用其它几种排序算法,Graham算法的复杂度都能达到\(O(n\log n)\)。采用快速排序,平均复杂度是\(O(n\log n)\),在C++中,提供了qsort()快速排序的算法,但在最坏情况下,Graham算法的复杂度仍然是\(O({{n}^{2}})\)。因此,可以选择归并排序或者堆排序。

表8.3 有关排序算法的分析结果

2015-3-24 10-29-36

 

spacer

One comment on “8.3. Graham扫描算法

Leave a reply