浏览量:166

6.6. 凸多边形的极点

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

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

6.6. 凸多边形的极点

问题描述:给定一个凸多边形\(P=\{{{V}_{0}},{{V}_{1}},\cdots ,{{V}_{n-1}}\}\),求\(P\)沿着方向\(\vec{d}\)上的极点,设\(P\)是逆时针顺序且不存在连续的三个顶点共线的情况。

对于任意一个点集和方向,通过测试每个点,可以在线性时间内得到。但对于凸多边形这种特殊的情况,它沿着任意一个方向,都是一个单调多边形,可以分成两条单调的多边形链,可以应用二分搜索的思想,在时间内找到极点[4,21]

2015-3-23 18-50-55

图6.38 凸多边形上的顶点投影到方向是\(\vec{d}\)的直线上

为了后面的算法论述,先对一些概念进行介绍。如图6.38所示,直线\(L\)所在的方向是\(\vec{d}\),把\(P\)上的顶点都投影到直线上,所有的投影点都介于\(\left[ \pi ({{V}_{\min }}),\pi ({{V}_{\max }}) \right]\)之间,则顶点\({{V}_{\min }}\)和顶点\({{V}_{\max }}\)分别称为凸多边形沿着方向\(\vec{d}\)最小极点最大极点。若点\([{{V}_{a}}\)在直线L上的投影点在点\({{V}_{b}}\)的投影点的正方向上,就称相对于\(\vec{d}\)\({{V}_{a}}\)\({{V}_{b}}\)的上方;反之,就称相对于\(\vec{d}\)\({{V}_{a}}\)\({{V}_{b}}\)的下方。图6.38中,相对于\(\vec{d}\)\({{V}_{i}}\)\({{V}_{j}}\)的上方,\({{V}_{i}}\)\({{V}_{i+1}}\)的下方。若凸多边形\(P\)上的边\(e={{V}_{a+1}}-{{V}_{a}}\),有\(\vec{d}\cdot e\succ 0\),就称\({{V}_{a}}\)相对于方向\(\vec{d}\)正向延伸;相反,若\(\vec{d}\cdot e\prec 0\),就称\({{V}_{a}}\)相对于方向\(\vec{d}\)负向延伸的,在不会引起歧义的情况下,可以简称为正向延伸和负向延伸。图6.38中,顶点\({{V}_{i}}\)是正向延伸的。

针对这个问题,最容易想到的一种算法是测试每个顶点到方向\(\vec{d}\)上的投影距离,取得距离最小的顶点和最大的顶点,算法复杂度是\(O(n)\),这种朴素算法的伪码如下所示:

给定一个凸多边形\(P=\{{{V}_{0}},{{V}_{1}},\cdots ,{{V}_{n-1}}\}\),求\(P\)沿着方向\(\vec{d}\)上的最大极点,设\(P\)是逆时针顺序。
1.    min = max = 0;
2.    for( i = 0 ; i < n ; i ++)
3.           if \(\vec{d}\cdot ({{V}_{i}}-{{V}_{\max }})\succ 0\), then
4.                  max = i;
5.           else if \(\vec{d}\cdot ({{V}_{i}}-{{V}_{\min }})\prec 0\), then
6.                  min = i;
7.           end if;
8.    end for;

也可应用二分搜索的思想,在\(O(\log n)\)时间内找到极点,但算法就相对复杂了些。现在考虑求最大极点,设最大极点在多边形链\({{V}_{a}}{{V}_{b}}\)之间,用区间\(\left[ a,b \right]=\left\{ a,a+1,\cdots ,a+k=b(\bmod n) \right\}\),表示多边形链\({{V}_{a}}{{V}_{b}}\)之间顶点的索引序列,其中\(k\succ 0\)。用\({{V}_{m}}\)表示多边形链\({{V}_{a}}{{V}_{b}}\)的中点,其中\(m=(a+b)/2\),则极大极点的索引值在\(\left[ a,m \right]\)之间或者在\(\left[ m,b \right]\)之间。若\({{V}_{m}}\)是最大极点,那么就不需要后续的判断,\({{V}_{m}}\)是凸多边形\(P\)的最大极点的判定条件是

\[\left\{ \begin{array}{l}\vec d \cdot ({V_{m + 1}} - {V_m}) \le 0\\\vec d \cdot ({V_m} - {V_{m - 1}}) \ge 0\end{array} \right. \tag{6.12}\]

2015-3-23 18-51-30

图6.39区间选择的6种情况

因为不存在连续的三个顶点共线的情况,所以两个不等式的等号不会同时成立。若中点\({{V}_{m}}\)并非所求的点,就需要判断最大极点位于哪个区间内,我们可以分成6种情况进行讨论,如图6.39所示:

1.     若\({{V}_{a}}\)正向延伸

    1. \({{V}_{m}}\)是负向延伸,则最大极点位于区间\(\left[ a,m \right]\)内;
    2. \({{V}_{m}}\)是正向延伸且\({{V}_{m}}\)位于\({{V}_{a}}\)上方,则最大极点位于区间\(\left[ m,b \right]\)内;
    3. \({{V}_{m}}\)是正向延伸且\({{V}_{m}}\)位于\({{V}_{a}}\)下方,则最大极点位于区间\(\left[ a,m \right]\)内;

2.     若\({{V}_{a}}\)负向延伸

    1. \({{V}_{m}}\)是正向延伸,则最大极点位于区间\(\left[ m,b \right]\)内;
    2. \({{V}_{m}}\)是负向延伸且\({{V}_{m}}\)位于\({{V}_{a}}\)下方,则最大极点位于区间\(\left[ m,b \right]\)内;
    3. \({{V}_{m}}\)是负向延伸且\({{V}_{m}}\)位于\({{V}_{a}}\)上方,则最大极点位于区间\(\left[ a,m \right]\)内;

算法的起始阶段,可以指定\(a=0,b=n\)来表示整个凸多边形,因为可以保证\(a\prec b\),所以\(0\le a\le m=\left\lfloor \left( a+b \right)/2 \right\rfloor \prec b\le n\)。第一次迭代,都会将区间减半,或者是把\(a\)增大至\(m\),或者是\(b\)\(P\)小至\(m\)。算法的伪码如下所示:

给定一个凸多边形\(P=\{{{V}_{0}},{{V}_{1}},\cdots ,{{V}_{n-1}}\}\),求\(P\)沿着方向\(\vec{d}\)上的最大极点,设\(P\)是逆时针顺序且不存在连续的三个顶点共线的情况
1.    \(a=0,b=n\);
2.    \(upA=\vec{d}\cdot \left( {{V}_{1}}-{{V}_{0}} \right)\);
3.    if \(upA\le 0\) and \(\vec{d}\cdot \left( {{V}_{0}}-{{V}_{n-1}} \right)\ge 0\), then
4.           return 0;
5.    end if;
6.    while( TRUE )
7.           \(m=\left( a+b \right)/2\);
8.           \(upM=\vec{d}\cdot \left( {{V}_{next(m)}}-{{V}_{m}} \right)\);                       //\(next(m)\equiv (m+1)%n\)
9.           if \(upM\le 0\) and \(\vec{d}\cdot \left( {{V}_{m}}-{{V}_{m-1}} \right)\ge 0\);   //可以确保\(m\succ 0\)
10.                 return \(m\);
11.          end if;
12.          if \(upA\succ 0\), then                                //点\({{V}_{a}}\)正向延伸
13.                 if \(upM\prec 0\), then                        //点\({{V}_{m}}\)负向延伸,选择\(\left[ a,m \right]\)
14.                        \(b=m\);
15.                 else if \(\vec{d}\cdot \left( {{V}_{a}}-{{V}_{m}} \right)\succ 0\), then       //\(upM\ge 0\)\({{V}_{m}}\)\({{V}_{a}}\)下方,选择\(\left[ a,m \right]\)
16.                        \(b=m\);
17.                 else                                            //\(upM\ge 0\)\({{V}_{m}}\)\({{V}_{a}}\)上方,选择\(\left[ m,b \right]\)
18.                        \(a=m\);
19.                        \(upA=upM\);
20.                 end if;
21.          else                                            //点\({{V}_{a}}\)负向延伸
22.                 if \(upM\succ 0\), then                        //点\({{V}_{m}}\)正向延伸,选择\(\left[ m,b \right]\)
23.                        \(a=m\);
24.                        \(upA=upM\);
25.                 else if \(\vec{d}\cdot \left( {{V}_{a}}-{{V}_{m}} \right)\prec 0\), then       //\(upM\le 0\)\({{V}_{m}}\)\({{V}_{a}}\)上方,选择\(\left[ a,m \right]\)
26.                        \(b=m\);
27.                  else                                            //\(upM\le 0\)\({{V}_{m}}\)\({{V}_{a}}\)下方,选择\(\left[ m,b \right]\)
28.                        \(a=m\);
29.                        \(upA=upM\);
30.                 end if;
31.          end if;
32.   end while;

2015-3-23 18-51-44

图6.40 二分搜索法求凸多边形的最大极点示例

以图6.40所示为例,来分析二分搜索法求凸多边形最大极点的算法过程。算法起始阶段,初始化\(a=0,b=11\),由于点\({{V}_{0}}\)不是最大极点,进入while循环;第一次进入算法第7步,\(m=5\)\({{V}_{a}}\)负向延伸,\({{V}_{m}}\)正向延伸,选择区间\(\left[ 5,11 \right]\);第2次进入算法第7步,\(a=5,b=11,m=8\)\({{V}_{a}}\)正向延伸,\({{V}_{m}}\)正向延伸,\({{V}_{m}}\)\({{V}_{a}}\)的上方,选择区间\(\left[ 8,11 \right]\);第3次进入算法第7步,\(a=8\)\(b=11,m=9\),点\({{V}_{m}}\)满足等式(6.12)的判定条件,因此确定点\({{V}_{m}}\)是凸多边形\(P\)的最大极点。

spacer

Leave a reply