浏览量:236

6.9. 简单多边形的凸包化

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

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

6.9. 简单多边形的凸包化

问题描述:将给定的简单多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)凸包化。

求给定点集的凸包的算法下限是\(O(n\log n)\),但是将简单多边形凸包化的算法复杂度是线性的。McCallum&Avis[28] (1979)提出了第一个正确的、线性复杂度的算法,后来的学者进一步对这个问题进行研究,提出了更为简单、高效、易懂的算法[29,30,31,32,33,34],其中Melkman[34] 在1987年提出的线性算法是最好的,因为该算法不考虑简单多边形的朝向,实现简单、高效,只使用一个双端队列即可。

2015-3-23 21-14-19

图6.48 简单多边形\({\rm P}\)的凸包化

如图6.48所示,就是由一个简单多边形\({\rm P}\)凸包化得到的凸多边形\(CH({\rm P})\),显然,多边形\({\rm P}\)在\(CH({\rm P})\)内部,而且构成\(CH({\rm P})\)的点集是构成\({\rm P}\)的点集的子集。

接下来,详细介绍Melkman算法,该算法主要用到的数据结构是双端队列,可以表示为\(deque=\{{{d}_{bott}},\cdots ,{{d}_{top}}\}\),\(bott\)表示队列的底部,\(top\)表示队列的顶部,而且有\({{d}_{top}}={{d}_{bott}}\)。对队列有4种操作:

  1. \(deque.\operatorname{push}\_back(v)\),将元素\(v\)存入队列顶部,执行的操作是:\(top=top+1,{{d}_{top}}=v\);
  2. \(deque.\operatorname{pop}\_back()\),将顶部的元素弹出,执行的操作是:\(top=top-1\];
  3. \(deque.\operatorname{push}\_front(v)\],将元素\(v\)存入队列底部,执行的操作是:\(bott=bott+1,{{d}_{bott}}=v\);
  4. \(deque.\operatorname{pop}\_front()\),将底部的元素弹出,执行的操作是\(bott=bott-1\)。

函数\(\operatorname{ORIENTATION}({{v}_{0}},{{v}_{1}},{{v}_{2}})\)实现的功能是判断点\({{v}_{2}}\)是否在由\({{v}_{0}},{{v}_{1}}\)确定的直线的右侧,如果在,返回1;如果三点\({{v}_{0}},{{v}_{1}},{{v}_{2}}\)共线,返回0;否则,返回-1,伪码如下所示:

\(\operatorname{ORIENT}({{v}_{0}},{{v}_{1}},{{v}_{2}})\)
/* \({{v}_{0}},{{v}_{1}},{{v}_{2}}\)表示三个点 */
1.    \(d=({{v}_{2}}-{{v}_{0}})\times ({{v}_{1}}-{{v}_{0}})\);
2.    if \(d\prec 0\), then
3.           return -1;
4.    else if \(d\succ 0\), then
5.           return 1;
6.    else
7.           return 0;
8.    end if;

简单多边形凸包化的Melkman算法的伪码如下所示:

求给定简单多边形\({\rm P} = \{ {V_0},{V_1}, \cdots ,{V_{n – 1}}\} \)凸包化后的凸多边形
1.      \(top=-1,bott=0\);
2.    if \(\operatorname{ORIENT}({{V}_{0}},{{V}_{1}},{{V}_{2}})\succ 0\), then                 //设初始的3个点\({{V}_{0}},{{V}_{1}},{{V}_{2}}\)不共线
3.           \(deque.\operatorname{push}\_back({{V}_{0}})\);
4.           \(deque.\operatorname{push}\_back({{V}_{1}})\);
5.    else
6.           \(deque.\operatorname{push}\_back({{V}_{1}})\);
7.           \(deque.\operatorname{push}\_back({{V}_{0}})\);
8.    end if;
9.    \(deque.\operatorname{push}\_back({{V}_{2}})\);
10.   \(deque.\operatorname{push}\_front({{V}_{2}})\);
11.   \(k=3\);
12.   while(\(k\prec n\))
13.          while(\(k\prec n\]&&\(\operatorname{ORIENT}({{d}_{bott}},{{d}_{bott+1}},{{V}_{k}})\ge 0\]&&\(\operatorname{ORIENT}({{d}_{top-1}},{{d}_{top}},{{V}_{k}})\ge 0\))
14.                 \(k+=1\);
15.          end while;
16.          if \(k\ge n\), then
17.                 break;
18.          end if;
19.          while(\(\operatorname{ORIENT}({{d}_{top-1}},{{d}_{top}},{{V}_{k}})\le 0\))
20.                 \(deque.\operatorname{pop}\_back()\);
21.          end while;
22.          \(deque.\operatorname{push}\_back({{V}_{k}})\);
23.          while(\(\operatorname{ORIENT}({{d}_{bott}},{{d}_{bott+1}},{{V}_{k}})\le 0\))
24.                 \(deque.\operatorname{pop}\_front()\);
25.          end while;
26.          \(deque.\operatorname{push}\_front({{V}_{k}})\);
27.          \(k+=1\);
28.   end while;

2015-3-23 21-14-32

图6.49 Melkman算法示例

以图6.49所示的简单多边形\({\rm P}\)为例,为了叙述方便,称双端队列顶部的两个点构成的边\(\overline{{{d}_{top-1}}{{d}_{top}}}\)为顶部边,称队列底部的两个点构成的边\(\overline{{{d}_{bott}}{{d}_{bott+1}}}\)为底部边。Melkman算法的初始阶段,\({{V}_{0}},{{V}_{1}},{{V}_{2}}\)是顺时针方向的,双端队列为\(deque=\{{{V}_{2}},{{V}_{0}},{{V}_{1}},{{V}_{2}}\}\);第1次while循环,处理顶点\({{V}_{3}}\),它在顶部边\(\overline{{{V}_{1}}{{V}_{2}}}\)的左侧,进入算法第19~21步的迭代,弹出队列顶部元素,直至点\({{V}_{3}}\)在顶部边右侧为止,而点\({{V}_{3}}\)在底部边的右侧,未进入第23~25步对队列底部的弹出操作,第1次while循环执结束时,\(deque=\{{{V}_{3}},{{V}_{2}},{{V}_{0}},{{V}_{1}},{{V}_{3}}\}\);第2次while循环,处理顶点\({{V}_{4}}\),它在底部边\(\overline{{{V}_{3}}{{V}_{2}}}\)的左侧,未进入算法第19~21步的迭代,但进入第23~25步的迭代,弹出队列的底部元素,直至点\({{V}_{4}}\)在底部边的右侧为止,第2次循环结束时,\(deque=\{{{V}_{4}},{{V}_{0}},{{V}_{1}},{{V}_{3}},{{V}_{4}}\}\);第3次while循环,处理顶点\({{V}_{5}}\),也是类似的算法过程,循环结束时,\(deque=\{{{V}_{5}},{{V}_{0}},{{V}_{1}},{{V}_{3}},{{V}_{4}},{{V}_{5}}\}\);第4次while循环结束时,\(deque=\{{{V}_{6}},{{V}_{0}},{{V}_{1}},{{V}_{3}},{{V}_{6}}\}\);第5次while循环结束时,\(deque=\{{{V}_{7}},{{V}_{6}},{{V}_{0}},{{V}_{1}},{{V}_{7}}\}\);第6次while循环结束时,\(deque=\{{{V}_{8}},{{V}_{7}},{{V}_{6}},{{V}_{0}},{{V}_{8}}\}\)。至此,多边形\({\rm P}\]上的所有顶点都处理结束,最终得到的凸多边形为\(CH({\rm P}) = \{ {V_7},{V_6},{V_0},{V_8}\} \)。

2015-3-23 21-14-43

图6.50 算法第13~15步排除的点\({{V}_{12}}\)

显然,从上面的例子中,我们可以发现\(deque\)中的点集构成包围当前已遍历顶点的凸多边形,首先假设这条结论是正确的,那么,在算法13~15步,排除的点在凸多边形\(deque\)内。如果一个点\(v\)被排除,那么它满足条件\(\operatorname{ORIENT}({{d}_{bott}},{{d}_{bott+1}},v)\ge 0\wedge \operatorname{ORIENT}({{d}_{top-1}},{{d}_{top}},v)\ge 0\),即点\(v\)在顶部边\(\overline{{{d}_{top-1}}{{d}_{top}}}\)的右侧且也在底部边\(\overline{{{d}_{bott}}{{d}_{bott+1}}}\)的右侧,连接点\(v\)与\({{d}_{top}}\)(或\({{d}_{bott}}\)),由于多边形\({\rm P}\)是简单的,所以边\(\overline{v{{d}_{top}}}\)一定不可能与\({{d}_{bott+1}}\)到\({{d}_{top-1}}\)的多边形链相交,举个例子,如图6.50所示,算法已处理了顶点\({{V}_{0}}\)~\({{V}_{11}}\),则\(deque=\{{{V}_{11}},{{V}_{0}},{{V}_{2}},{{V}_{4}},{{V}_{5}},{{V}_{9}},{{V}_{10}},{{V}_{11}}\}\),对于接下来要处理的顶点\({{V}_{12}}\),它在边\(\overline{{{V}_{11}}{{V}_{0}}}\)和边\(\overline{{{V}_{10}}{{V}_{11}}}\)的右侧,一定在凸多边形\(deque\)内。

接着,证明\(deque\)中的点集构成包围当前已遍历顶点的凸多边形。算法第2~10步,可以得到初始的、不共线的、由3个点构成的凸多边形\(deque\),如果顶点在算法13~15步被排除,那么它一定在当前凸多边形\(deque\)内,如果顶点未被排除,设顶点为\(v\),算法第19~26步,更新\(deque\),得到新的多边形链\(deque’=\{{{d}_{bott’}},\cdots ,{{d}_{top’}}\}\),其中\({{d}_{bott’}}={{d}_{top’}}=v\),。由于多边形\(deque\)是简单的,如果\(deque’\)是非简单的,只有可能是\(\overline{v{{d}_{bott’+1}}}\)或\(\overline{{{d}_{top’-1}}v}\)与多边形\(deque\)的边相交,由于多边形\({\rm P}\)是简单的,所以相交一定不可能发生,那么\(deque’\]也是简单的。对于当前的多边形\(deque’\),有\(\operatorname{ORIENT}({{d}_{k}},{{d}_{k+1}},{{d}_{k+2}})\succ 0,k=bott’,\cdots ,top’-2\),否则,在算法第19~26步会弹出相应的点,只有可能出现\(\operatorname{ORIENT}({{d}_{top’-1}},v,{{d}_{bott’+1}})\le 0\),如果出现这种情况,说明顶点\(v\)在边\(\overline{{{d}_{top’-1}}{{d}_{bott’+1}}}\)的右侧,而顶点\(v\)又在多边形链\(\{{{d}_{bott’+1}},\cdots ,{{d}_{top’-1}}\}\]的右侧,所以顶点\(v\)在凸多边形\(deque\),产生矛盾。综上所述,\(deque’\)也是凸多边形。顶点\(v\)在凸多边形\(deque\)外,每次将\(deque\)中的点弹出,连接\(v\)与凸多边形\(deque\)上的点,都会扩大凸多边形,易知\(deque’\)包含\(deque\)。

spacer

Leave a reply