浏览量:103

7.3. 凸多边形的宽

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

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

7.3. 凸多边形的宽

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

凸多边形的由多边形上距离最近的、互相平行的两条支撑线确定,支撑线之间的距离就是凸多边形的宽,如图7.8所示。Houle&Toussaint[5](1988)提出了两种求点集宽的算法,本节将描述其中与旋转测径相关的算法。

2015-3-23 21-41-08

图7.8 对互相平行的支撑线确定的宽

定理7.3.   多边形\({\rm P}\)的宽由\({\rm P}\)上距离最近的点-边对踵对确定。

证明:可以分成两种情况来分析。

1. 点-点对踵对

给定任意两点\(p\)\(q\),通过它们的支撑线分别是\({{l}_{1}}\)\({{l}_{2}}\),那么将支撑线分别沿着\(p\)\(q\)绕着某个方向旋转,可以使得支撑线之间的距离降低。如图7.9所示,将两条支撑线沿着逆时针方向旋转,它们间的距离会减小,直至一条支撑线与\({\rm P}\)的一条边重合为止。因此,点-点对踵对不能确定多边形的宽。

2015-3-23 21-41-18

图7.9 点-点对踵对的支撑线

2. 边-边对踵对

此时,宽表示为一条边上的一个顶点与另一条边所在的支撑线之间的距离,所以这可以看成是点-边对踵对的特殊情况。

 

通过旋转测径法,得到所有的点-边对踵对,其中距离最小的点-边对踵对确定凸多边形的宽,时间复杂度是\(O(n)\),算法伪码如下所示:

给定一个凸多边形\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n - 1}}\} \),求凸多边形的宽,设凸多边形是逆时针顺序
1.    \(m=-\infty \);
2.    for( i=1 ; i<n ; i++ )
3.           if \(area({{p}_{n-1}},{{p}_{0}},{{p}_{i}})\succ m\), then                   //\(area({{p}_{0}},{{p}_{1}},{{p}_{2}})\equiv ({{p}_{1}}-{{p}_{0}})\times ({{p}_{2}}-{{p}_{0}})\)
4.                  k = i;
5.                  m = \(area({{p}_{n-1}},{{p}_{0}},{{p}_{i}})\);
6.           end if;
7.    end for;
8.    \(w=m/\left\| {{p}_{0}}-{{p}_{n-1}} \right\|\);
9.    for( i = 1 ; i < n ; i++ )
10.          \(m=area({{p}_{i-1}},{{p}_{i}},{{p}_{k}})\);
11.          while(1)
12.                 if \(area({{p}_{i-1}},{{p}_{i}},{{p}_{next(k)}})\prec m\), then           //\(next(k)\equiv (k+1)%n\)
13.                        break;
14.                 else
15.                        \(m=area({{p}_{i-1}},{{p}_{i}},{{p}_{next(k)}})\);
16.                        \(k=next(k)\);
17.                 end if;
18.          end while;
19.          if \(w\succ m/\left\| {{p}_{i}}-{{p}_{i-1}} \right\|\), then
20.                 \(w=m/\left\| {{p}_{i}}-{{p}_{i-1}} \right\|\);
21.          end if;
22.   end for;
23.   return w;

对于计算点集的宽的问题,可以在\(O(n\log n)\)时间内找到包围点集的凸多边形,然后通过旋转测径法在线性时间内计算点集宽,算法效率受凸包算法的限制,时间复杂度是\(O(n\log n)\)

spacer

Leave a reply