浏览量:331

7.2. 凸多边形的直径

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

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

7.2. 凸多边形的直径

问题描述:给定一个凸多边形\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \),求凸多边形的直径。

凸多边形的直径是指凸多边形上相距最远的两点之间的距离,现在考虑如果确定凸多边形的直径呢?引入一个重要的理论:

定理7.1.  凸多边形\({\rm P}\)的直径可以由两条距离最远的、互相平行的支撑线来确定,该支撑线之间的距离等于\({\rm P}\)的直径大小。

证明:给定一个凸多边形\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \),设点对\(\{ {p_a},{p_b}\} \)可以确定凸多边形\({\rm P}\)的直径,则\({{d}_{ab}}=\operatorname{dist}({{p}_{a}},{{p}_{b}})\)\({{C}_{a}}\)表示以\({{p}_{a}}\)为原点,\({{d}_{ab}}\)为半径的圆,\({{C}_{b}}\)表示以\({{p}_{b}}\)为原点,\({{d}_{ab}}\)为半径的圆,直线\({{L}_{a}}\)\({{C}_{b}}\)相切于点\({{p}_{a}}\),直线\({{L}_{b}}\)\({{C}_{a}}\)相切于点\({{p}_{b}}\)\(L\)表示为连接点\({{p}_{a}}\)\({{p}_{b}}\)的线段,如图7.3所示。由直线与圆相切的性质,知\({{L}_{a}}\bot L,{{L}_{b}}\bot L\),因此直线\({{L}_{a}}\)\({{L}_{b}}\)互相平行。随机选择一个点\(q \in {\rm P},q \ne {p_a}\),由直径的定义知\(\operatorname{dist}(q,{{p}_{b}})\le {{d}_{ab}}\),则\(q\)在圆\({{C}_{b}}\)上或者圆\({{C}_{b}}\)内,所以\(q\notin {{L}_{a}}\),即凸多边形\({\rm P}\)内除点\({{p}_{a}}\)外,不存在点在直线\({{L}_{a}}\)上,易知\({{L}_{a}}\)\({\rm P}\)的一条支撑线。同理,可以得到直线\({{L}_{b}}\)也是\({\rm P}\)的一条支撑线。

2015-3-23 21-40-11

图7.3 由对踵对确定的凸多边形直径

直线\({{L}_{a}}\)\({{L}_{b}}\)\({\rm P}\)上互相平行的支撑线,则有\({\mathop{\rm diameter}\nolimits} ({\rm P}) = {d_{ab}} = {\mathop{\rm dist}\nolimits} ({L_a},{L_b})\)。现在假设存在两条支撑线\({{L}_{1}},{{L}_{2}}\),有\(\operatorname{dist}({{L}_{1}},{{L}_{2}})\succ {{d}_{ab}}\),该支撑线分别与\({\rm P}\)相交于\({{q}_{1}},{{q}_{2}}\),则有\(dist({{q}_{1}},{{q}_{2}})\)\(\ge dist({{L}_{1}},{{L}_{2}})\succ {{d}_{ab}}\),这与\({{d}_{ab}}=dist({{p}_{a}},{{p}_{b}})\).是凸多边形\({\rm P}\)的直径矛盾。至此,结论得证。

 

由上面的理论,我们可知凸多边形\({\rm P}\)的直径是\({\rm P}\)上距离最远的点-点对踵对,只要找到所有可能的点-点对踵对,其中距离最远的点对,就是\({\rm P}\)的直径。Preparata&Shamos[4](1985)描述了一种应用旋转测径思想实现的求凸多边直径的算法,算法的伪码如下所示:

给定一个凸多边形的\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \),求凸多边形的直径,设凸多边形为逆时针顺序,且不存在连续的k(k>2)个顶点共线
1.    i = n - 1;
2.    j = 0;
3.    while(\(\operatorname{area}({{p}_{i}},{{p}_{next(i)}},{{p}_{next(j)}})\succ \operatorname{area}({{p}_{i}},{{p}_{next(i)}},{{p}_{j}})\))             //\(area({{p}_{0}},{{p}_{1}},{{p}_{2}})\equiv ({{p}_{1}}-{{p}_{0}})\times ({{p}_{2}}-{{p}_{0}})\)
4.           j = next(j);                                                       // next(i) = (i + 1) % n
5.    end while;
6.    q = j;
7.    i = next(i);
8.    d = -1.0;                                                                 //凸多边形的直径
9.    while( j != 0 && i <= q)
10.          d =\(dist({{p}_{i}},{{p}_{j}})\)> d ?\(dist({{p}_{i}},{{p}_{j}})\): d;
11.          while(\(area({{p}_{i}},{{p}_{next(i)}},{{p}_{next(j)}})\succ area({{p}_{i}},{{p}_{next(i)}},{{p}_{j}})\) )
12.                 j = next(j);
13.                 if  i != q || j != 0, then
14.                        d =\(dist({{p}_{i}},{{p}_{j}})\)> d ?\(dist({{p}_{i}},{{p}_{j}})\): d;
15.                 else
16.                        return d;
17.                 end if;
18.          end while;
19.          if \(area({{p}_{i}},{{p}_{next(i)}},{{p}_{next(j)}})==area({{p}_{i}},{{p}_{next(i)}},{{p}_{j}})\), then
20.                 if  i != q || j != n-1 , then
21.                        d =\(dist({{p}_{i}},{{p}_{next(j)}})\) > d ?\(dist({{p}_{i}},{{p}_{next(j)}})\): d;
22.                 else
23.                        d =\(dist({{p}_{next(i)}},{{p}_{j}})\) > d ?\(dist({{p}_{next(i)}},{{p}_{j}})\): d;
24.                        return d;
25.                 end if;
26.          end if;
27.          i = next(i);
28.   end while;
29.   return d;

2015-3-23 21-40-24

图7.4 旋转测径法求凸多边形直径举例

以图7.4所示的凸多边形\({\rm P}\)为例,算法第1~6步,找到\({\rm P}\)上距离边\(\overline{{{p}_{9}}{{p}_{0}}}\)最远点\({{p}_{5}}\),令\(q=5,i=0\);算法第9步,\(i=0,j=5\),第一次进入while循环,距离边\(\overline{{{p}_{0}}{{p}_{1}}}\)最远的点是\({{p}_{5}}\),执行完一次循环体后,即算法第10~26步,得到点-点对踵对\(\left( {{p}_{0}},{{p}_{5}} \right)\);算法第9步,\(i=1,j=5\),边\(\overline{{{p}_{1}}{{p}_{2}}}\)与边\(\overline{{{p}_{6}}{{p}_{7}}}\)互相平行,得到点-点对踵对\(\left( {{p}_{1}},{{p}_{5}} \right),\left( {{p}_{1}},{{p}_{6}} \right),\left( {{p}_{1}},{{p}_{7}} \right)\);算法第9步,\(i=2,\)\(j=6\),距离边\(\overline{{{p}_{2}}{{p}_{3}}}\)最远的点是\({{p}_{9}}\),得到点-点对踵对\(\left( {{p}_{2}},{{p}_{6}} \right),\left( {{p}_{2}},{{p}_{7}} \right),\left( {{p}_{2}},{{p}_{8}} \right),\)\(\left( {{p}_{2}},{{p}_{9}} \right)\);算法第9步,\(i=3,j=9\),距离边\(\overline{{{p}_{3}}{{p}_{4}}}\)最远的点是\({{p}_{9}}\),得到点-点对踵对\(\left( {{p}_{3}},{{p}_{9}} \right)\);算法第10步,\(i=4,j=9\),得到点-点对踵对\(\left( {{p}_{4}},{{p}_{9}} \right)\);算法第9步,\(i=5,j=9\),执行第一次算法第11步的循环后,得到点-点对踵对\(\left( {{p}_{5}},{{p}_{9}} \right)\),此时\(i=5,j=0\),进入算法第16步,算法结束。

2015-3-23 21-40-35

图7.5 把凸多边形分解为多边形链

现在需要证明算法的正确性,即需要验证上述算法确实能生成多边形\({\rm P}\)所有的对踵对。考虑与顶点\({{p}_{i}}\)相关联的所有点-点对踵对,令\({{p}^{-}}\)是距离边\(\overline{{{p}_{i-1}}{{p}_{i}}}\)最远的点,\({{p}^{+}}\)是距离边\(\overline{{{p}_{i}}{{p}_{i+1}}}\)最远的点,如图7.5所示,较粗的实线表示多边形的边,多边形链\({{p}_{i+1}}{{p}^{-}}\)\({{p}^{-}}{{p}^{+}}\)\({{p}^{+}}{{p}_{i-1}}\)分别在区域A、区域B、区域C内。可以得到:

定理7.2.   与顶点\({p_i}\)相关联的所有点-点对踵对在多边形链\({p^ - }{p^ + }\)上。

证明:设\({{p}_{0}}\)在多边形链\({{q}^{-}}{{q}^{+}}\)外,但是能与顶点\({{p}_{i}}\)形成点-点对踵对,先考虑\({{p}_{0}}\)在区域A内,如图7.6所示,经过点\({{p}_{0}}\)的直线要成为支撑线,该直线不能与凸多边形\({\rm P}\)相交,深色区域表示所有经过点\({{p}_{0}}\)的支撑线。同理,浅色区域表示所有经过点\({{p}_{i}}\)的支撑线。深色区域和浅色区域没有交集,易知,不存在经过点\({{p}_{0}}\)的支撑线与经过点\({{p}_{i}}\)的支撑线互相平行的情况,即\({{p}_{0}}\)\({{p}_{i}}\)不可能是点-点对踵对。若点\({{p}_{0}}\)在区域C中,也可以用类似的方法证明。

 

2015-3-23 21-40-45

图7.6 在区域A中,与点\({{p}_{i}}\)、点\({{p}_{0}}\)关联的支撑线可能所在的区域

2015-3-23 21-40-59

图7.7 在区域B中,与点\(q\)、点\({{p}_{0}}\)关联的支撑线可能所在的区域

考虑在多形边链\({{q}^{-}}{{q}^{+}}\)之间的点\(q\),如图7.7所示,深色区域表示所有经过点\(q\)的支撑线,浅色区域表示所有经过点\({{p}_{i}}\)的支撑线,深色区域与浅色区域存在重叠。不论点\(q\)在区域B中的哪个位置,总能找到两条分别经过点\(q\)和点\({{p}_{i}}\),且互相平行的支撑线,即点\(q\)和点\({{p}_{i}}\)是点-点对踵对。

 

上述算法确定了距离边\(\overline{{{p}_{i-1}}{{p}_{i}}}\)最远的点\({{p}^{-}}\),距离边\(\overline{{{p}_{i}}{{p}_{i+1}}}\)最远的点\({{p}^{+}}\),处理多边形链\({{p}^{-}}{{p}^{+}}\)之间的点与点\({{p}_{i}}\)形成的点-点对踵对,处理一周后回到原点,生成多边形\({\rm P}\)上所有的点-点对踵对。旋转测径法计算凸多边形的直径的复杂度是\(O(n)\),互相平行的边最多有\(\left\lfloor n/2 \right\rfloor \)对,点-点对踵对最多有\(3n/2\)[4]

对于计算点集的直径问题,可以在\(O(n\log n)\)时间内得到包围点集的凸多边形,参见第九章,再通过旋转测径法在线性时间内计算出凸多边形的直径,算法效率受凸包算法的限制,时间复杂度是\(O(n\log n)\)

spacer

Leave a reply