浏览量:524

6.3. 多边形判定

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

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

6.3. 多边形判定

判断一个多边形是否是简单的,关键在于怎么判断多边形的边是否存在自相交,Shamos-Heoy[25](1976)提出了一种复杂度为\(O(n\log n)\)判断线段集是否存在相交的算法,可应用于判定一个多边形是否是简单的[27],可以采用第四章的Shamos-Hoey算法。判断一个简单多边形是否是单调的,Preparata&Supowit[16](1981)提出一种最优的性线复杂度的算法。判断一个多边形是否是凸的,如果先判断多边形是否是简单的,再判断是否存在大于180度的内角,算法需要\(O(n\log n)\)的时间,但Schorn& Fisher [1](1994)提出了一种最优的线性算法。

本小节将会介绍简单多边形的单调性和多边形的凸性判定算法。

6.3.1. 简单多边形的单调性

问题描述:判定二维空间上的简单多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)是否是单调的,设简单多边形是逆时针顺序的。

2015-3-23 16-33-48

图6.20 边与边的夹角

我们这里规定,边\({{e}_{0}}\)与边\({{e}_{1}}\)的夹角记为\(({{e}_{0}},{{e}_{1}})\),它的绝对值小于180度,如图6.20所示(a),边\({{e}_{1}}\)在边\({{e}_{0}}\)的逆时针方向,则边\({{e}_{0}}\)与边\({{e}_{1}}\)的夹角大于0度,即\(({{e}_{0}},{{e}_{1}})\succ 0\);如图(b)所示,边\({{e}_{1}}\)在边\({{e}_{0}}\)的顺时针方向上,夹角小于0度,即\(({{e}_{0}},{{e}_{1}})\prec 0\)

设多边形的边\({{e}_{i}}=\overline{{{V}_{i}}{{V}_{i+1}}}\),令\({{C}_{0}}=\left( (1,0),{{e}_{0}} \right)\)\({{C}_{k}}=\sum\limits_{i=1}^{k}{({{e}_{i-1}},{{e}_{i}})},1\le k\le n-1\),称\({{C}_{k}}\)就是边\({{e}_{k}}\)的极角坐标,在极角坐标\({{C}_{i}}\)\({{C}_{j}}\)之间会形成一个扇形区域,极角坐标\({{C}_{i}}\)沿着逆时针方向旋转至\({{C}_{j}}\)的扇形区域记为\(({{C}_{i}},{{C}_{j}})\)

2015-3-23 16-34-04

图6.21 简单多边形和它对应的极角坐标图

如图6.21示,图(a)是多边形\({\rm P}\),图(b)是它对应的极角坐标图。对于极角坐标图,我们可以想像为初始情况下有一条边\({{e}_{0}}\),把它看成类似于手表上的指针一样的有向向量,将它沿逆时针旋转角度\(\left\| ({{e}_{0}},{{e}_{1}}) \right\|\)至边\({{e}_{1}}\)的极角坐标\({{C}_{1}}\),再顺时针旋转角度\(\left\| ({{e}_{1}},{{e}_{2}}) \right\|\)至边\({{e}_{2}}\)的极角坐标\({{C}_{2}}\),依次类推,直至完成所有夹角的旋转,形成完整的极角坐标图。也可以换一个角度理解极角坐标图,它相当于把多边形上的每条边看成向量,将它们的起始位置移至顶点\({{V}_{0}}\)。显然,极角坐标将\([0,2\pi )\)分割成一个个的扇形区域,有些扇形区域会被扫描1次,有些区域会被扫描2次或者多次。如图1.22(b)所示,\(({{C}_{2}},{{C}_{1}})\)\(({{C}_{4}},{{C}_{3}})\)被扫描了3次,区域\(({{C}_{4}},{{C}_{1}})\)\(({{C}_{3}},{{C}_{5}})\)只被扫描了1次,我们称扫描的次数为该扇区的重数(multiplicity)。

在介绍完基本概念后,引入单调多边形的判定定理:

若简单多边形\({\rm P}\)是单调的,当且仅当它对应的极角坐标图中,存在重数为1的扇区。

证明:这里先证明一条引理:设\(\{{{e}_{0}},{{e}_{1}},\cdots ,{{e}_{k}}\}\)是一条多边形链,它相对于直线\(L\)是单调的当且仅当\(L\)的法向量\(\vec{n}\)不在重数大于等于1的扇区。

用反证法来证明,设\(L\)的法向量\(\vec{n}\)在该区域中,则至少存在一个连续边形成的扇区,设为\(({{C}_{k}},{{C}_{k+1}})\),使得\(\vec{n}\)在该区域内。如图1.22所示,显然相对于点\({{V}_{k+1}}\)\({{V}_{k}}\)\({{V}_{k+2}}\)在直线上的投影在相同的一侧,那么多边形链相对于直线\(L\)不是单调的,与题设矛盾。因此,多边形链\(\{{{e}_{0}},{{e}_{1}},\cdots ,{{e}_{k}}\}\)相对于直线\(L\)是单调的,当且仅当\(L\)的法向量\(\vec{n}\)不在重数大于等于1的扇区。

2015-3-23 16-34-18

图6.22 引理的证明

如果简单多边形\({\rm P}\)是单调的,当且仅当存在直线\(L\),可以把多边形\({\rm P}\)分为两个单调的多边形链。显然,如果至少存在一个重数为1的扇区,那么简单多边形\({\rm P}\)相对于法向量在该扇区的直线\(L\)单调。

2015-3-23 16-34-33

图6.23 夹角计算

首先,我们需要考虑边与边的夹角的计算,设函数\(\operatorname{COMPUTE}\_ANGLE({{e}_{0}},{{e}_{1}})\)实现的功能就是计算夹角\(({{e}_{0}},{{e}_{1}})\),采用等式\(\theta =\operatorname{asin}\left( \left( {{e}_{0}}\times {{e}_{1}} \right)/\left( \left\| {{e}_{0}} \right\|\cdot \left\| {{e}_{1}} \right\| \right) \right)\)计算出介于\([-\pi /2,\pi /2]\)的角度值,如图6.23所示,如果边\({{e}_{0}},{{e}_{1}}\)同向,如图(a)(c)所示,则夹角为\(\theta \);如果不同向且\(\theta \succ 0\),如图(b)所示,则夹角为\(\pi -\theta \);否则,如图(d)所示,则夹角为\(-(\pi +\theta )\)

算法的伪码如下所示:

\(\operatorname{COMPUTE}\_ANGLE({{e}_{0}},{{e}_{1}})\)
1.    \(\theta =\operatorname{asin}\left( \left( {{e}_{0}}\times {{e}_{1}} \right)/\left( \left\| {{e}_{0}} \right\|\cdot \left\| {{e}_{1}} \right\| \right) \right)\)
2.    if \({{e}_{0}}\cdot {{e}_{1}}\succ 0\), then
3.           return \(\theta \);
4.    else if \(\theta \succ 0\), then
5.           return \(\pi -\theta \);
6.    else
7.           return \(-(\pi +\theta )\);
8.    end if;

可以用一个双向循环链表,来存储极角坐标,此外还需要存储一个计数器,用于记录扇区的重数,即双向循环链表中存储的节点的数据结构为\(\{angle,count\}\),其中\(angle\)表示极角坐标,极角坐标的取值范围是\([0,2\pi )\)\(count\)表示扇区重数。因为我们只需要找到重数为\(1\)的扇区,重数等于2或大于2的区域,可以统一标识为2,所以\(count\)的取值范围是\(\{0,1,2\}\)。令极角坐标\({{C}_{0}}=0\),并不会影响到算法的结果。

算法的基本过程如下所示:

  1. 初始情况下,扇区\([0,2\pi )\)的重数为0,双向循环链表为空,令\({{C}_{0}}=0\),表示当前的极角坐标为0;
  2. 计算边\({{e}_{k}}\)与边\({{e}_{k+1}}\)的夹角\({{\alpha }_{k}}=({{e}_{k}},{{e}_{k+1}})\),如果\({{\alpha }_{k}}\succ 0\),将当前指针沿逆时针旋转至新的极角坐标,即在当前节点向后遍历链表,找到合适的位置,插入新的节点;如果\({{\alpha }_{k}}\succ 0\),则沿着顺时针旋转,即在当前节点向前遍历,找到合适的位置,插入新节点。设新的极角坐标为\({{C}_{k}}={{C}_{k-1}}+{{\alpha }_{k}}\),更新当前节点为极角坐标为\({{C}_{k}}\)的节点。在遍历的过程中,如果存在相邻的两个扇区的重数相同,则把它们合并为一个。如图6.24所示,当前极角坐标为\({{C}_{a}}\),新的夹角为\(({{C}_{a}},{{C}_{g}})\),在往后遍历链表的过程中,使得其间的扇区重数都增加1,合并重数相同的相邻扇区,此时链表中仅存有极角坐标为\(\{{{C}_{a}},{{C}_{g}},{{C}_{h}}\}\)的节点。
  3. 重复第2步操作,直至多边形\({\rm P}\)上的所有夹角处理完成;
  4. 如果存重数为1的扇区,则多边形\({\rm P}\)为单调的;否则,不单调。

2015-3-23 16-34-49

图6.24 合并重数相同的相邻扇区

算法伪码如下所示:

判定二维空间上的简单多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)是否是单调的,设简单多边形是逆时针顺序的
{TRUE, FALSE}
1.    head = {0, 0}, tail = {\(2\pi \), 0}
2.    初始化双向循环链表List为空;
3.    List.initialize(head);                                         //把节点head存入链表List中
4.    List.insert_back(head, tail);                               //在链表List的节点head后插入节点tail
5.    polar = 0;
6.    current = tail;
7.    for( i = 0 ; i < n ; i += 1 )
8.           e0 = V[(i + 1) % n] V[i];
9.           e1 = V[(i + 2) % n] V[(i + 1) % n];
10.          angle = COMPUTE_ANGLE(e0, e1);
11.          if angle > 0, then                                             //逆时针扫描
12.                 if current.angle ==\(2\pi \), then
13.                        current = List.next(current);         //链表List中节点current的下一个节点
14.                 end if;
15.                 current = INSERT_CCW(current, polar, angle);
16.          else if angle < 0, then                                      //顺时针扫描
17.                 current = INSERT_CW(current, polar, angle);
18.          end if;
19.          polar = CLAMP_ANGLE(polar + angle);    //把极角坐标限制在\([0,2\pi )\)范围内,
20.   end for;
21.   for 双向循环链表List中的每一个元素node
22.          if node.count == 1, then
23.                 return TRUE;
24.          end if;
25.   end for;
26.   return FALSE;

函数INSERT_CCW(head, polar, angle)的伪码如下所示:

INSERT_CCW(head, polar, angle)             ////逆时针方向插入夹角
/* head是双向循环链表中的一个节点,head.angle小于等于极角坐标polarpolar表示极角坐标,取值介于\([0,2\pi )\)angle表示夹角,取值介于\((0,\pi )\)*/
1.    sum = polar + angle;
2.    current = head;
3.    if sum >\(2\pi \), then
4.           current = INSERT_CCW(current, polar,\(2\pi \)- polar);
5.           current = List.next(current);                       //链表List中节点current的下一个节点
6.           node = INSERT_CCW(current, 0, sum -\(2\pi \));
7.    else
8.           next = List.next(current);
9.           while(next.angle < sum)
10.                 current.count = (current.count < 2? current.count + 1: 2);
11.                 current = next;
12.                 next = List.next(current);
13.          end while;
14.          if next.angle != sum, then
15.                 if current.count < 2, then
16.                        node.count = current.count;
17.                        node.angle = sum;
18.                        current.count = (current.count < 2? current.count + 1: 2);
19.                        List.insert_back(current, node);
20.                 else
21.                        node = current;
22.                 end if;
23.          else
24.                 current.count = (current.count < 2? current.count + 1: 2);
25.                 node = next;
26.          end if;
27.          if head != node, then                   //合并链表中从headnode,计数器值相同的节点
28.                 current = head;
29.                 next = List.next(current);
30.                 while(next != node)
31.                        tm = List.next(next);
32.                        if( current.count == next.count ), then
33.                               List.erase(next);
34.                        end if;
35.                        next = tm;
36.                 end while;
37.          end if;
38.   end if;
39.   return node;

函数INSERT_CW(head, polar, angle)的伪码如下所示:

INSERT_CW(head, polar, angle)               //顺时针方向插入夹角
/* head是双向循环链表中的一个节点,head.angle小于等于极角坐标polarpolar表示极角坐标,取值介于\([0,2\pi )\)angle表示夹角,取值介于\((0,\pi )\)*/
1.    sum = polar + angle;
2.    current = head;
3.    if sum < 0, then
4.           if polar != 0, then
5.                  current = INSERT_CW(current, polar, -polar);
6.           end if;
7.           current = List.pre(current);                  //链表List中节点current的前一个节点
8.           node = INSERT_CW(current, \(2\pi \), sum);
9.    else
10.          next = null;
11.          while(current.angle > sum)
12.                 if next != null, then
13.                        current.count = (current.count < 2? current.count + 1: 2);
14.                 end if;
15.                 next = current;
16.                 current = List.pre(current);
17.          end while;
18.          if current.angle != sum, then
19.                 if current.acount < 2, then
20.                        node.angle = sum;
21.                        node.count =  (current.count < 2? current.count + 1: 2);
22.                        List.insert_back(current, node);
23.                 else
24.                        node = current;
25.                 end if;
26.          else
27.                 current.count = (current.count < 2? current.count + 1: 2);
28.                 node = current;
29.          end if;
30.          if head != node, then
31.                 current = head;
32.                 pre = List.pre(current);
33.                 while(pre != node)
34.                        if current.count == pre.count, then
35.                               List.erase(current);
36.                        end if;
37.                        current = pre;
38.                        pre = List.pre(current);
39.                 end while;
40.          end if;
41.   end if;
42.   return node;

6.3.2. 多边形的凸性

问题描述:判定二维空间上的多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)是否是凸的,设多边形是逆时针顺序的。

一种很朴素的算法就是先判断一个多边形是否是简单多边形,再判断是否存在内角大于180度,这种算法的复杂度是\(O(n\log n)\),Schorn& Fisher [1](1994)提出了一种更加简单的判定方法。

       如果多边形\({\rm P}\)满足下面的3个条件,则说明该多边形是凸的:

  1. 任意两个连续的顶点不相同,即\(\forall i,{{V}_{i}}\ne {{V}_{i+1}},0\le i\prec n\),其中\({{V}_{0}}={{V}_{n}}\)
  2. 定义顶点的大小关系:\(p < q \Leftrightarrow ({p_x} < {q_x}) \vee (({p_x} = {q_x}) \wedge ({p_y} < {q_y}))\)。易知,所有的凸多边形都有一定的单调性,如果顶点\({{V}_{i}},...,{{V}_{j}}\)是单调递增的,顶点\({{V}_{j}},...,{{V}_{k}}\)是单调递减的或者先递减后递增,称这种变化为一次单调跳变。用\(c\)来统计单调跳变的次数,凸多边形一定有\(c\le 2\)
  3. 多边形\({\rm P}\)相邻3个顶点的夹角不大于180。设\(d(i)=({{V}_{i-1}}-{{V}_{i}})\times ({{V}_{i+1}}-{{V}_{i}})\),其中\({{V}_{-1}}={{V}_{n-1}}\)\({{V}_{n}}={{V}_{0}}\),如果\(d(i)\prec 0\),则夹角\(\angle {{V}_{i-1}}{{V}_{i}}{{V}_{i+1}}\)大于180,否则,不大于180。凸多边形一定满足条件

\(\left( \forall i:0\le i\prec n,d(i)\ge 0 \right)\wedge \left( \exists i:0\le i\prec n,d(i)\succ 0 \right)\)

  若\(\forall i:0\le i\prec n,d(i)=0\),说明多边形\({\rm P}\)上的顶点共线。

条件1较容易理解,后面的讨论默认满足该条件。条件3限制了多边形的顶点只能绕着顺时针或者逆时针方向旋转,如果既存在顺时针朝向的顶点链也存在逆时针的顶点链,那么在它们发生朝向跳变的那个点所在的夹角大于180。但是,如果只满足条件3,不满足条件2,就可能发生图6.25(a)所示的情况,顶点绕着同一个方向旋转,可边发生了交叉。条件2限制了顶点绕着顺时针或者逆时针方向旋转的周期,单调跳变次小于等于2,保证顶点链只能旋转一周。但是,如果只满足条件2,不满足条件3,就会发生图(b)所示的情况,多边形的内角大于180

2015-3-23 16-35-08

图6.25 退化情况,(a)多边形的相邻3个顶点的夹角小于180,(b)单调跳变的次数小于等于2

算法伪码如下所示:

       判定二维空间上的多边形\(\text{P}=\{{{V}_{0}},{{V}_{1}},...,{{V}_{n\text{-}1}}\}\)是否是凸的,设多边形\(\text{P}\)是逆时针顺序的
return ({TRUE, FALSE})
1.    s = COMPARE(\({{V}_{n-1}},{{V}_{0}}\));   //若\({{V}_{n-1}}={{V}_{0}}\),返回0;若\({{V}_{n-1}}\prec {{V}_{0}}\),返回1;否则,返回-1
2.    count = 0;
3.    for ( i = 0 ; i < n - 1 ; i += 1 )
4.           t = COMPARE (\({{V}_{i}},{{V}_{i+1}}\));
5.           if t == 0, then                                                 //判定条件1
6.                  return FALSE;
7.           else if t != s, then                                      //判定条件2
8.                  count += 1;
9.                  s = t;
10.                 if count > 2, then
11.                        return FALSE;
12.                 end if;
13.          end if;
14.   end for;
15.   isOnLine = TRUE;                                           //判定多边形是否退化成一条线
16.   for ( i = 0 ; i < n ; i++ )                                          //判定条件3
17.          angle = \(({{V}_{i+1}}-{{V}_{i}})\times ({{V}_{i-1}}-{{V}_{i}})\);                      //令\({{V}_{n}}={{V}_{0}},{{V}_{-1}}={{V}_{n-1}}\)
18.          if angle < 0 , then
19.                 return FALSE;
20.          else if (isOnLine && angle > 0), then
21.                 isOnLine = FALSE;
22.          end if;
23.   end for;
24.   return isOnLine? FALSE: TRUE;

spacer

One comment on “6.3. 多边形判定

  1. Anonymous

    太好了,一直想找一个比较好的学习计算几何的教程,感觉您的这些文章特别适合我这个初学者,感谢!

Leave a reply