浏览量:1,141

6.2. 多边形生成算法

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

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

6.2. 多边形生成算法

6.2.1. 生成算法综述

随机多边形的生成主要有两个应用:a)测试算法的正确性;b)评估算法耗费的CPU时间。为了能评估算法的正确性,输入的数据应尽可能的分散,使得算法的每一个分支都得到执行,这也有利于算法效率的有效评估。但实际上,我们经常很难获得大量有效的输入数据来测试,因此随机多边形的生成算法就显得非常的必要。

给定一个点集,求由它们组成的均匀分布的简单多边形是一个NP难问题,至今还没有找到多项式级别的算法,但对某些特殊的多边形,存在有多项式级别的算法。我们也可以采用启发式的方法,在可以接受的时间范围内生成丰富多样的非均匀分布的简单多边形。这里先介绍下非均匀分布的概念,设存在\(n\)个点的点集,总共能生成\(m\)种简单多边形,均匀分布的简单多边形生成算法是指这\(m\)种简单多边形都会有一定概率被生成,但非均匀分布的生成算法,只能生成其中的\(k(k\prec m)\)种。

针对随机星状多边形的生成算法,早在1988就Linda&hute[10]就提出了一种\(O({{n}^{5}})\)的生成算法,Sohler[15](1999)提出了另一种时间复杂度更低的生成算法,达到\(O({{n}^{2}}\log n)\),Auer& Held[12](1996)提出了两种星状多边形的生成算法,一个算法复杂度是\(\text{O(}{{\text{n}}^{5}}\log n)\),和前面两种算法类似,实现难度较大,另外一个算法简单易实现,但不能保证生成的星状多边形可能是非退化的,称它为快速星状生成算法,复杂度是\(O(n\log n)\),本节将会详细地描述快速星状生成算法。

针对随机单调多边形的生成算法,Zhu et al[11](1996)提出了一种通过上顶点链表和下顶点链表,生成随机的X单调多边形,算法的复杂度是\(O(n)\),但是需要\(O({{n}^{2}})\)的预处理时间。本小节将会详细地描述另外一种更简单的生成算法,可以生成任意直线方向上的单调多边形。

针对随机凸多边形的生成算法,一种很简单的方法,就是随机生成一组点,通过凸包算法,求出包围点集的凸多边形。但是,这种方法会造成的一个问题是:随机生成10000个点数据,最终得到的凸包可能只有100个顶点,甚至于更少。Devillers et al[20](2014)提出了一种生成在同一个圆盘上的凸多边形,本节将介绍一种更简单的基于圆盘的凸多边形生成算法。

针对随机简单多边形的生成算法,由于无法在多项式时间内生成均匀分布的简单多边形,但是我们可以通过启发式的方法,生成非均匀分布的简单多边形。Auer&Held[12](1996)提出了多种启发式的方法,包括稳定增长法(Steady Growth)、空间分割法(Space Partition)、两步移动法(2-opt Moves),复杂度分别是\(O({{n}^{2}})\)、\(O(n\log n)\)和\(\text{O(}{{\text{n}}^{4}}logn)\)。此外,Dailey& Whitfield[14](2008)提出了一种\(O({{n}^{2}}\log n)\),类似于Koth曲线的构造,使用到多边形三角剖分算法。本节将介绍稳定增长法、两步移动法、和空间分割生成算法。

6.2.2. 星状多边形的生成算法

问题描述:随机生成不重合的\(n\)个点的点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),由该点集生成一个逆时针顺序的星状多边形。

随机确定一个点\(P\),要求点\(P\)在点集\(S\)所确定的凸包内,可知点集\(S\)的中心,一定在凸包内,即

\[P = \frac{1}{n}\sum\limits_{i = 0}^{n – 1} {{P_i}} \tag{6.1}\]

2015-3-23 15-10-45

图6.5 点集的排序

若\(P\in S\),从点集中将点\(P\)移除,即\(S’=S-\left\{ P \right\}\)。对点集\(S’\)绕着点\(P\)沿着逆时针方向排序,即根据边\(\overline{P{{P}_{i}}}\)与经过点\(P\),方向是(0,1)的直线的逆时针上的极角从小到大排序,若极角相同,与点\(P\)距离远的点在前,近的点在后。以图6.5所示的10个点的排序为例,点的索引号就表示排序后的点的顺序。\(\overline{P{{P}_{0}}}\)与直线的极角小于90且最小;\(\overline{P{{P}_{4}}}\)和\(\overline{P{{P}_{5}}}\)与直线的极角均大于90、小于180且相等,此时距离较远的点\({{P}_{4}}\)排在前;此外,\({{\overline{PP}}_{6}}\tilde{\ }\overline{P{{P}_{9}}}\)与直线的夹角均大于180,所以排在较后。

按极角从小到大排序后,每个极角上选择一个点,作为多边形的顶点,若存在多个点的极角相同,任取一个点,但为了使核尽可能的大,可以选择与点\(P\)最远的点。以图6.5所示为例,可以取\({{P}_{4}}\)作为该极角的代表。易知,所有的顶点对点\(P\)都可见。

算法的伪码如下所示:

随机产生不重合的\(n\)个点的点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),由该点集生成一个逆时针的星状多边形
1.    \(P=\frac{1}{n}\sum\limits_{i=0}^{n-1}{{{P}_{i}}}\);
2.    if \(P\in S\), then
3.           \(S’=S-\{P\}\);
4.    else
5.           \(S’=S\);
6.    end if;
7.    将\(S’\)绕P,沿逆时针方向排序;
8.    遍历排序后的点集\(S’\),每个极角取与\(P\)距离最远的点,得到单调多边形的顶点序列;

2015-3-23 15-11-03

图6.6 快速星状算法生成的星状多边形,(a)点集个数为10,(b)点集个数为50,(c)点集个数为200

算法的时间复杂度是\(O(n\log n)\),图6.6就是采用快速星状生成算法生成的星状多边形。显然,随着点集(点集的数据范围相同)个数的增加,生成的星状多边形的核的面积越来越小,将会无限趋近于中心点\(P\),但总能保证对点\(P\)是可见的。

6.2.3. 单调多边形的生成算法

问题描述:随机生成不重合的\(n\)个点的点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),由该点集生成一个沿直线\(L\)方向逆时针顺序的单调多边形,直线\(L\)的参数方程是\(L(t)=P+t\cdot \vec{d}\)。

因为单调多边形与只与直线的方向有关,可以取\(P=(0,0)\)。把点集投影到直线\(L\)上,根据在直线上的投影长度从小到大的顺序对点集排序,投影长度的计算等式为

\[{b_i} = \vec d \cdot {P_i},0 \le i \prec n \tag{6.2}\]

2015-3-23 15-11-13

图6.7 计算点集的投影长度,并对点集排序

以图6.7所示为例,计算出点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{6}} \right\}\)在直线上的投影长度,然后按照从小到大的顺序排序,排序的结果为\({{P}_{0}},{{P}_{1}},\cdots ,{{P}_{6}}\)。

设排序后的点集顺序为\({{Q}_{0}},{{Q}_{1}},\cdots ,{{Q}_{n-1}}\),连接起始点\({{Q}_{0}}\)和终止点\({{Q}_{n-1}}\),得到分割线段\(\overline{{{Q}_{0}}{{Q}_{n-1}}}\),取\(S’=S-\{{{Q}_{0}},{{Q}_{n-1}}\}\)。依顺序遍历点集\(S’\)的每个点\({{Q}_{i}}(1\le i\le n-2)\),以线段\(\overline{{{Q}_{0}}{{Q}_{n-1}}}\)所在的直线为分割边界,若点\({{Q}_{i}}\)满足条件:\( ({{Q}_{n-1}}-{{Q}_{0}})\times ({{Q}_{i}}-{{Q}_{0}})\succ 0\),说明它在分割边界的上方;反之,说明它在分割边界下方。据此,把点集\(S’\)分成两个子集\({{S}_{top}}=\left\{ {{T}_{0}},{{T}_{1}},\cdots ,{{T}_{k-1}} \right\}\)和\({{S}_{bottom}}=\left\{ {{B}_{0}},{{B}_{1}},\cdots ,{{B}_{l-1}} \right\}\],\(l+k=n-2\),最终生成的单调多边形为\(\{{{Q}_{0}},{{B}_{0}},{{B}_{1}},\cdots ,{{B}_{l-1}},{{Q}_{n-1}},\)\({{T}_{k-1}},{{T}_{k-2}},\cdots ,{{T}_{1}},{{T}_{0}}\}\)。

以图6.7为例,由起始点与终止点构成的分割线段\(\overline{{{P}_{0}}{{P}_{6}}}\),把点集分为两个子集\({{S}_{top}}=\left\{ {{P}_{2}},{{P}_{4}},{{P}_{5}} \right\}\)和\({{S}_{bottom}}=\left\{ {{P}_{1}},{{P}_{3}} \right\}\),最终生成的单调多边形为\(\left\{ {{P}_{0}},{{P}_{1}},{{P}_{3}},{{P}_{6}},{{P}_{5}},{{P}_{4}},{{P}_{2}} \right\}\)。

算法伪码如下所示:

随机产生不重合的\(n\)个点的点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),由该点集生成一个沿直线\(L\)方向逆时针顺序的单调多边形,设直线的参数方程是\(L(t)=P+t\cdot \vec{d}\)
1.    定义一个名为Node的数据结构,表示为\(\{idx,len\}\),其中,\(idx\)记录点的索引值,\(len\)记
录点在直线\(L\)上的投影长度;
2.    定义一个Node类型的对象长度为\(n\)的数组\(node\);
3.    for( \(i=0\) ; \(i\prec n\) ; \(++i\))
4.           \(node[i].idx=i\);
5.           \(node[i].len=\vec{d}\cdot {{P}_{i}}\);
6.    end for;
7.    以投影长度从小到大的顺序,对\(node\)数组排序;
8.    初始化链表\({{S}_{top}}\)和\({{S}_{bottom}}\)为空;
9.    \(\vec{b}={{P}_{node[n-1].idx}}-{{P}_{node[0].idx}}\);
10.   for( \(i=1\) ; \(i\prec n-1\) ; \(++i\) )
11.          if \(\vec{b}\times ({{P}_{node[i].idx}}-{{P}_{node[0].idx}})\succ 0\), then
12.                 \({{S}_{top}}.push\_front({{P}_{node[i].idx}})\);
13.          else
14.                 \({{S}_{bottom}}.push\_back({{P}_{node[i].idx}})\);
15.          end if;
16.   end for;
17.   单调多边形为\(\left\{ {{P}_{node[0].idx}},{{S}_{bottom}},{{P}_{node[n-1].idx}},{{S}_{top}} \right\}\);
2015-3-23 15-11-28

图6.8 随机生成的单调多边形,(a)X单调多边形,点集个数是50,(b)X单调多边形,点集个数是100,(c)Y单调多边形,点集个数是100

算法的时间复杂度为\(O(n\log n)\),可以求出点集沿着任意一个方向的单调多边形。如图6.8所示,就是几个采用上述算法生成的单调多边形,单调链分布在分割线段的两侧,不存在跨越分割线段的边。

6.2.4. 凸多边形的生成算法

问题描述:随机生成\(n\)个点构成的逆时针顺序的凸多边形。

依次连接一个圆上的点,可以得到一个凸多边形,算法的伪码可以表示为:

随机生成\(n\)个点构成的逆时针顺序的凸多边形,凸多边形的顶点在同一个圆上,给定圆的中心\(O\),半径\(r\)
1.    s = 0;
2.    for( \(i=0\) ; \(i\prec n\] ; \(++i\))
3.           \(angle[i]=\]random(\(l,h\));                //随机生成一个介于\((l,h),l\succ 0\)之间的实数
4.           \(s+=angle[i]\);
5.    end for;
6.    c = 0;
7.    for( \(i=0\) ; \(i\prec n\) ; \(++i\) )
8.           \(c+=angle[i]\];
9.           \(V[i].x\)=\(-\sin (2\pi \cdot \text{c/s)}\cdot r+O.x\);
10.          \(V[i].y\)= \(\cos (2\pi \cdot \text{c/s)}\cdot r+O.y\);
11.   end for;
12.   凸多边形为\(\{V[0],V[1],\cdots ,V[n-1]\}\);

2015-3-23 15-53-26

图6.9 随机生成凸多边形

如图6.9所示,就是采用上述算法生成的凸多边形。只要随机生成一个角度,给定圆的半径和圆心,计算出顶点,最后连接各个顶点,就得到一个凸多边形。

6.2.5. 简单多边形的生成算法

问题描述:随机生成不重合的\(n\)个点的点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),由该点集生成一个逆时针顺序的简单多边形。

方法一稳定增长法

CH(S)表示包围点集\(S\]的凸多边形,算法主要分为四个步骤:

  1. 从点集\(S\)中任取三个点\(\left\{ {{P}_{{{i}_{0}}}},{{P}_{{{i}_{1}}}},{{P}_{{{i}_{2}}}} \right\}\),构成初始的简单多边形\({{T}_{1}}\),需要保证\({{T}_{1}}\)中不包含点集中的其它点,令\({{S}_{1}}=S-\left\{ {{P}_{{{i}_{0}}}},{{P}_{{{i}_{1}}}},{{P}_{{{i}_{2}}}} \right\}\);
  2. 从\({{S}_{m}},i\ge 1\)中任取一个点\({{P}_{i}}\),从点集\({{S}_{m}}\)中移除该点\({{S}_{m+1}}={{S}_{m}}-\{{{P}_{i}}\}\),保证\({{S}_{m+1}}\)中不存在点在\(CH({{T}_{m}}\bigcup \{{{P}_{i}}\})\)内;
  3. 从简单多边形\({{T}_{m}}\)中找到一条边\(\overline{{{V}_{k}}{{V}_{k+1}}}\],使得它对点\({{P}_{i}}\)完全可见,然后把该边替换为\(\overline{{{V}_{k}}{{P}_{i}}}\)和\(\overline{{{P}_{i}}{{V}_{k+1}}}\),得到新的简单多边形\({{T}_{m+1}}\);
  4. 若\({{S}_{m+1}}\)不为空,重复算法第2~3步。

2015-3-23 15-53-39

图6.10 简单多边形上不存在对点\(P\)完全可见的边

满足第2步的点\({{P}_{i}}\)总是可以找到,这保证了第3步中简单多边形至少存在一条边对点\({{P}_{i}}\)完全可见。若点P在简单多边形T外,对它完全可见的边不总是存在,如图6.10所示,点\(P\)在简单多边形外,但不存在对它完全可见的边。可如果点\(P\)在\(CH(T)\)外,则一定存在这样的边,我们可以简单的证明下这条结论。

证明:点\(P\)在\(CH(T)\)外,可以找到与点\(P\)相切的两个顶点,它们对点\(P\]可见,如图6.11所示的顶点\({{V}_{i}}\)和\({{V}_{k}}\)。若简单多边形T上,介于顶点\({{V}_{i}}\)和\({{V}_{k}}\)之间只有一条边,显然边\(\overline{{{V}_{i}}{{V}_{k}}}\)对点\(P\)完全可见。若至少有\(k\)条边介于它们之间,如果与最左边的点\({{V}_{i}}\)关联的边\({{e}_{i}}\)对点\(P\)完全可见,得到可见边;相反,若非完全可见,找到阻挡边\({{e}_{i}}\)且对\(P\)可见的点\({{V}_{j}}\)。现在考虑顶点\({{V}_{j}}\)与\({{V}_{k}}\)之间的边,依次推导下去,一定可以得到对点\(P\)完全可见的边。

2015-3-23 15-53-51

图6.11 若点\(P\)在凸包\(CH(T)\)外,则简单多边形\(T\)上至少存在一条对点\(P\)完全可见的边

算法的第1步,得到初始的由三个点构成的简单多边形,可以在线性时间内完成;算法的第2步和第3步,均可以在线性时间内完成,每个点都需要\(O(n)\)的处理时间,整个算法的复杂度是\(O({{n}^{2}})\)。

方法二两步移动法

对点集\(S\)进行随机排列,得到初始的多边形,若该多边不存在自相交,则得到简单多边形,否则,需要移除相交。若两条边\(\overline{{{V}_{i}}{{V}_{i+1}}}\)和\(\overline{{{V}_{j}}{{V}_{j+1}}}\)发生相交,改变两条边的连接,例如改成\(\overline{{{V}_{i}}{{V}_{j}}}\)和\(\overline{{{V}_{i+1}}{{V}_{j+1}}}\),使它们不再相交,称这一个过程为两步移动操作。重复两步移动操作,直至多边形不存在自相交为止,就得到一个简单多边形。两步移动法主要分为四个步骤:

  1. 找到自相交的边\({{e}_{1}}\)和边\({{e}_{2}}\);
  2. 确定相交的类型;
  3. 改变边的连接,移除相交;
  4. 若多边形中还存在相交,重复第1~3步,直至得到简单多边形。

至此,存在三个问题有待解决:a)边与边的相交类型有哪些,如何改变边的连接;b)改变两条相交边的连接,是否会由于引入新的相交,导致算法无法终止;c)算法的时间复杂度是否是多项式级别的。Leeuwen et al[9]在1980年对这几个问题进行了详细的解答,接下来分别进行介绍。

2015-3-23 15-54-11

图6.12 多边形自相交的三种类型,(a)常规相交,(b)边的顶点在与它不相邻的边上,(c)多条在同一条直线上的边发生重叠

多边形自相交的类型共有三种,如图6.12所示,虚线表示一条边或者多条边构成的多边形链,实线表示一条边。第1种相交,如图(a)所示,两条边互相交叉;第2种,如图(b)所示,一条边的顶点在与它不相邻的边上,边\(\overline{{{V}_{j}}{{V}_{j+1}}}\)上的顶点\({{V}_{j+1}}\)在边\(\overline{{{V}_{i}}{{V}_{i+1}}}\)上;第3种,如图(c)所示,多条边在同一条直线上,箭头表示边的方向,但是发生了重叠,例如边\(\overline{{{V}_{i}}{{V}_{j-1}}}\)与边\(\overline{{{V}_{j-1}}{{V}_{i+1}}}\)就发生了重叠。通过两步移动操作,左图出现的自相交情况,在右图中已不再出现。

2015-3-23 15-54-27

图6.13 与边相交的光束个数的统计

完全一次两步移动操作后,会用新的边替换相交边,此时可能就会引入新的相交,但幸运地是不管对以何种顺序对相交情况进行两步移动操作,算法都能在多项式级别的时间内终止。这里引入相交光束的概念,给定n个点的点集,任意两个点可以确定一条光束,可以把光束看成是一条无穷远的直线,设T是一条连接这些点集的多边形路径。T表示多边形,c(e)表示与多边形T中的边e相交的光束的个数,若一条光束与边e重合,则该相交计为2次,如图6.13所示,与多边形相交的光束总共为

\(c(T) = \sum\limits_{e{\rm{ of T}}} {c(e)} \)

n个点最多有\(n(n-1)/2\)条光束,一些光束计为2次,对于多边形T上的每条边e有\(c(e)\le 2\cdot n(n-1)/2\prec {{n}^{2}}\),则\(c(T)\prec {{n}^{3}}\)。也就是说,连接n个点的多边形,存在小于\({{n}^{3}}\)个自相交的情况。若每次移除多边形的一个自相交情况,会导致\(c(T)\)减少,那么最多只需要\({{n}^{3}}\)次移除就可以得到简单多边形。

设一条多边形\(T\)至少存在一个自相交,移除该相交后,得到新的多边形T’,则有c(T’) < c(T)。

证明:根据多边形自相交的3种类型来证明这条结论。

情况一.

2015-3-23 15-54-40

图6.14 相交类型1的两步位移操作

任意一条与边\({{f}_{1}},{{f}_{2}},{{e}_{1}},{{e}_{2}}\)不重合的光束b,若它与\({{e}_{1}}\)或\({{e}_{2}}\)相交,那么它必与\({{f}_{1}}\)或\({{f}_{2}}\)相交,即该光束b对\(c({{f}_{1}})+c({{f}_{2}})\)的贡献与对\(c({{e}_{1}})+c({{e}_{2}})\)的贡献是一样的。

考虑与4条边重合的光束,\(\lambda (a)\)表示与边\(a\)重合的光束个数,则可得到下面的等式:

\[\left\{ {\begin{array}{*{20}{l}}{c({f_1}) = }&{\lambda ({e_1}) + }&{2\lambda ({f_1}) + }&{\lambda ({f_2}) + }&{\lambda ({e_2})}\\{c({f_2}) = }&{\lambda ({e_1}) + }&{\lambda ({f_1}) + }&{2\lambda ({f_2}) + }&{\lambda ({e_2})}\\{c({e_1}) = }&{2\lambda ({e_1}) + }&{\lambda ({f_1}) + }&{\lambda ({f_2})}&{}\\{c({e_2}) = }&{}&{\lambda ({f_1}) + }&{\lambda ({f_2}) + }&{2\lambda ({e_2})}\end{array}} \right.\]

因此,有\(\left\{ c({{f}_{1}})+c({{f}_{2}}) \right\}-\left\{ c({{e}_{1}})+c({{e}_{2}}) \right\}=\lambda ({{f}_{1}})+\lambda ({{f}_{2}})\ge 2\)。

情况二.

2015-3-23 15-54-51

图6.15相交类型2的两步位移操作

任意一条与边\({{f}_{1}},{{f}_{2}},{{e}_{1}},{{e}_{2}}\)不重合的光束b,与相交类型1的情况类似,光束b对\(c({{f}_{1}})+c({{f}_{2}})\)的贡献与对\(c({{e}_{1}})+c({{e}_{2}})\)的贡献是一样的。

考虑与四条边重合的光束,可得到下面的式子:

\[\left\{ {\begin{array}{*{20}{l}}{c({f_1}) = }&{2\lambda ({f_1}) + }&{\lambda ({f_2}) + }&{\lambda ({e_2})}\\{c({f_2}) = }&{\lambda ({f_1}) + }&{2\lambda ({f_2}) + }&{\lambda ({e_2})}\\{c({e_1}) = }&{2\lambda ({f_1}) + }&{\lambda ({f_2})}&{}\\{c({e_2}) = }&{\lambda ({f_1}) + }&{\lambda ({f_2}) + }&{2\lambda ({e_2})}\end{array}} \right.\]

因此,有\(\left\{ {c({f_1}) + c({f_2})} \right\} – \left\{ {c({e_1}) + c({e_2})} \right\} = \lambda ({f_2}) \ge 1\)。

情况三.

2015-3-23 15-55-03

图6.16 相交类型3的两步位移操作

显然,\(c(T)-c(T’)=\sum\limits_{i=1}^{k}{\lambda ({{f}_{i}})}-\sum\limits_{i=1}^{k}{\lambda ({{e}_{i}})}\),其中\(k\ge 3\),任何对\(c(T’)\)有贡献的光束,对\(c(T)\)一定有贡献。由于边\({{f}_{i}},1\le i\le k\)之间存在重叠,设\({{f}_{i}},{{f}_{j}},1\le i,j\le k\)发生了重叠,一条光束b经过两条边的重叠区域,光束b对\(c(T)\)的贡献比\(c(T’)\)至少多1,即一定有\(c(T)-c(T’)\ge 1\)。

综上三种情况,可以得到\(c(T)-c(T’)\ge 1\)。

连接\(n\)个点的任意一个多边形,最多有\({{n}^{3}}\)个自相交,每次两步位移操作至少会减少一次自相交。因此,算法可以在\({{n}^{3}}\)次两步位移后,得到不相交的多边形,即得到一个简单多边形。

算法的第1步,找到一组自相交的边,至少需要的算法复杂度是\(O(n\log n)\)。所以两步位移法的算法复杂度是\(O({{n}^{4}}\log n)\)。

方法三空间分割法

空间分割法的基本思想是把点集递归的划分成两子集,每个子集形成一条多边形链,最终生成一个完整的简单多边形。算法主要可以分为下面几个步骤:

  1. 从点集S中随机挑选出两个点\({{P}_{i}},{{P}_{j}}\),将这两个点从点集S中排除\(S=S-\{{{P}_{i}},{{P}_{j}}\}\);
  2. 经过点\({{P}_{i}},{{P}_{j}}\)的直线用\(L({{P}_{i}},{{P}_{j}})\)表示,它把点集S分成\({{S}_{left}}\)和\({{S}_{right}}\)两个子集,用函数DIVIDE(S, \(L({{P}_{i}},{{P}_{j}})\), sign, \({{S}_{left}}\), \({{S}_{right}}\))表示;
  3. 若集合\({{S}_{left}}\)为空,直接输出两个点\({{P}_{i}},{{P}_{j}}\)。否则,从子集\({{S}_{left}}\)中随机取得一个点\({{P}_{k}}\)并把它从集合中移除\({{S}_{left}}={{S}_{left}}-\{{{P}_{k}}\}\),随机生成一个介于\(\overline{{{P}_{i}}{{P}_{j}}}\)之间的点\({{P}_{r}}\),它把点集\({{S}_{left}}\)分为两个子集,递归的处理两子集,求出每个子集生成的多边形链,并归并为一条完整的多边形链。这个过程用符号PARTITION(\({{S}_{left}}\),\(L({{P}_{r}},{{P}_{k}})\),\({{R}_{left}}\))表示,\({{R}_{left}}\)表示集合\({{S}_{left}}\)生成的多边形链。
  4. 对于子集\({{S}_{right}}\)的情况,与第3步的情况类似,生成多边形链\({{R}_{right}}\);
  5. 将多边形链\({{R}_{left}}\]和\({{R}_{right}}\)归并为一条多边形链。

2015-3-23 15-55-28

图6.17 空间分割法过程举例

以图6.17(a)所示的点集为例,第1步,随机选择两个点\({{P}_{0}}\)和\({{P}_{3}}\);第2步,直线\(L({{P}_{0}},{{P}_{3}})\)把剩下的点集分成两个子集\({{S}_{left}}=\{{{P}_{4}},{{P}_{5}},{{P}_{6}},{{P}_{7}}\}\)和\({{S}_{right}}=\{{{P}_{1}},{{P}_{2}}\}\);先考虑子集\({{S}_{left}}\),第3步,集合\({{S}_{left}}\)中随机选择一个点\({{P}_{6}}\),随机生成一个介于线段\(\overline{{{P}_{0}}{{P}_{3}}}\)之间的点\({{P}_{r}}\),直线\(L({{P}_{6}},{{P}_{r}})\)把点集再次分为两个子集\(\{{{P}_{5}},{{P}_{7}}\}\)和\(\{{{P}_{4}}\}\),如图(d)~(f)所示,算法会递归的处理每个子集,得到一条由集合\({{S}_{left}}\)和\(\{{{P}_{0}},{{P}_{3}}\}\)形成的多边形链;第4步,对于子集\({{S}_{right}}\),也是类似的处理,如图(g)~(i)所示,生成一条由集合\({{S}_{left}}\)和\(\{{{P}_{0}},{{P}_{3}}\}\)形成的多边形链;最后,第5步,把两个多边形链归并为一个完整的多边形链,算法结束。

算法的伪码表示如下所示:

随机生成不重合的n个点的点集\(S=\left\{ {{P}_{0}},{{P}_{1}},\cdots ,{{P}_{n-1}} \right\}\),由该点集生成一个逆时针顺序的简单多边形

1.    随机取两个点\({{P}_{i}}\)和\({{P}_{j}}\),\(S=S-\{{{P}_{i}},{{P}_{j}}\}\);
2.    DIVIDE(\(S\),\(L({{P}_{i}},{{P}_{j}})\), 1,\({{S}_{left}}\),\({{S}_{right}}\));
3.    PARTITION(\({{S}_{left}}\),\({{P}_{i}}\),\({{P}_{j}}\),\({{R}_{left}}\));
4.    PARTITION(\({{S}_{right}}\),\({{P}_{j}}\),\({{P}_{i}}\),\({{R}_{right}}\));
5.    \({{R}_{left}}\).pop_front ();
6.    \(R={{R}_{right}}\bigcup {{R}_{left}}\);

定义一个函数\(\operatorname{ORIENTATION}(p,q,r)\),如果\( (p,q,r)\)是逆时针顺序的,则返回1;如果是顺时针顺序,则返回-1;否则,说明三点共线,则返回0。

\(\operatorname{ORIENTATION}(p,q,r)\)
/*\(p,q,r\]分别表示3个点 */
1.    d = \( (q-p)\times (r-p)\);
2.    if d > 0, then
3.           return 1;
4.    else if d < 0, then
5.           return -1;
6.    else
7.           return 0;
8.    end if;

函数DIVIDE(S, \(L(p,q)\), sign, \({{S}_{left}}\), \({{S}_{right}}\))表示将点集S,根据分隔线\(L(p,q)\),划分为两个子集合\({{S}_{left}}\)和\({{S}_{right}}\),而在分隔线上的点被排除,它的伪码表示为:

DIVIDE(S, \(L(p,q)\), sign, \({{S}_{left}}\), \({{S}_{right}}\))
/* S表示输入点集,\(L(p,q)\)表示分隔线, sign表示符号位,\({{S}_{left}}\)和\({{S}_{right}}\)表示输出的点集*/
1.    for 点集S中的每个点r
2.           t = sign * \(\operatorname{ORIENTATION}(p,q,r)\);
3.           if t > 0, then
4.                  \({{S}_{left}}\).push_back(r);
5.           else if t < 0, then
6.                  \({{S}_{right}}\).push_back(r);
7.           end if;
8.    end for;

函数PARTITION (\(S\),\(L(p,q)\),\(R\))是一个递归方法,它的功能是将点集S生成多边形链R,它的伪码表示为:

PARTITION (\(S\),\(L(p,q)\),\(R\))
/*\(S\)表示输入点集,\(L(p,q)\)表示分隔线,\(R\)表示输出点集*/
1.    if \(S = = \emptyset \), then
2.           R.push_back(q);
3.           R.push_back(p);
4.           return;
5.    end if;
6.    从S中随机选择一个点\({{t}_{1}}\);
7.    S = S – {\({{t}_{1}}\)};
8.    随机生成一个数\(d,d\in (0,1)\);
9.    \({{t}_{0}}\)= p + (q – p) * d;
10.   sign =\(\operatorname{ORIENTATION}({{t}_{0}},{{t}_{1}},p)\);
11.   \({S_{left}} = \emptyset ,{S_{right}} = \emptyset \);
12.   DIVIDE(S,\(L({{t}_{0}},{{t}_{1}})\), sign,\({{S}_{left}}\),\({{S}_{right}}\));
13.   \({R_{left}} = \emptyset ,{R_{right}} = \emptyset \);
14.   PARTITION(\({{S}_{left}}\),\(L(p,{{t}_{1}})\),\({{R}_{left}}\));
15.   PARTITION(\({{S}_{right}}\),\(L({{t}_{1}},q)\),\({{R}_{right}}\));
16.   \({{R}_{left}}\).pop_front();
17.   R = \({{R}_{right}}\bigcup {{R}_{left}}\);

2015-3-23 15-55-46

图6.18 空间分割法生成的简单多边形,(a)点集个数为50,(b)点集个数为200,(c)点集个数为500

空间分割法的平均复杂度是\(O(n\log n)\),最坏情况下的复杂度是\(O({{n}^{2}})\)。空间分割法生成的简单多边形,如图6.18所示,该方法只能生成非均匀分布的简单多边形,即不能生成由点集构成的所有简单多边形,如图6.19所示的多边形,空间分割法就无法生成。

2015-3-23 15-55-57

图6.19空间分割法无法生成的简单多边形

spacer

Leave a reply