浏览量:573

6.8. 线性对象与凸多边形的交

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

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

6.8. 线性对象与凸多边形的交

Cyrus&Beck[8](1978)提出了一种判断直线与凸多边形相交测试的算法,该算法还可以解决三维空间上直线与凸多面体的相交测试问题,称之为Cyrus-Beck裁剪算法,Hill& Kelley[7](2008)中也有算法的描述,算法的复杂度为\(O(n)\)。

此外,针对凸多边形,可以应用二分查找,得到复杂度为\(O(\log n)\),判断直线与凸多边形的相交测试。

6.8.1. Cyrus-Beck裁剪算法

问题描述:线性对象\(L(t) = P + t\vec d\)与凸多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)的相交测试,设凸多边形逆时针顺序的。

如图6.42所示,线性对象不仅可以用参数方程的形式表示,而且还可以用法线形式来表示。设凸包上的一条边是,边上指向外侧的法向量是\(\vec n\),边所在的直线可用法线形式表示为:

\[\vec n \cdot (P – {V_i}) = 0 \tag{6.13}\]

把参数方程\(L(t)\)代入等式(6.13),得到:

\[\vec n(P + \hat t\vec d – {V_i}) = 0 \tag{6.14}\]

容易求出它们的交点,得:

\[\hat t = \frac{{\vec n \cdot ({V_i} – P)}}{{\vec n \cdot \vec d}} \tag{6.15}\]

2015-3-23 20-12-55

图6.42 线性对象与直线的相交

法向量与线性对象的方向向量点积的符号,可以确定线性对象的走向。若\(\vec{n}\cdot \vec{d}\prec 0\),说明线性对象沿着法向量相反的方向延伸;若\(\vec{n}\cdot \vec{d}\succ 0\),说明它沿着法向量相同的方向延伸;若\(\vec{n}\cdot \vec{d}=0\),说明两条线性对象是平行或者重合的。

当分母为0时,两条直线平行或者重合,就可以忽略相交点的计算。因为法向量的方向是指向凸包外,所以分子\(\vec{n}\cdot ({{V}_{i}}-P)\prec 0\),说明直线与凸多边形一定不相交,这一步判断可以减少不必要的相交计算。

边\(\overline{{{V}_{i}}{{V}_{i+1}}}\)指向外侧的法向量的计算,与凸多边形的顶点顺序相关。如果顶点是逆时针顺序的,指向外侧的法向量是\((y,-x)\);如果顶点是顺时针顺序的,法向量是\((-y,x)\)。

若一条线性对象与凸多边形相交,那么它一定进入多边形一次,离开多边形一次,共两次,有两个交点。如图6.43所示,进入多边形时相交点的\(t\]值,称为\({{t}_{in}}\);离开时相交点的\(t\)值,称为\({{t}_{out}}\)。设边上指向外侧的法向量是\(\vec{n}\),若\(\vec{n}\cdot \vec{d}\prec 0\),说明线性对象进入多边形;若\(\vec{n}\cdot \vec{d}\succ 0\),说明线性对象离开多边形。把\(t\]值代入线性对象的参数方程就可以求出交点,相交部分的线段介于\([{{t}_{in}},{{t}_{out}}]\)区间内,不仅解决了相交问题,还解决的线性对象的裁剪问题,这就是称它为裁剪算法的原因。

2015-3-23 20-13-05

图6.43 线性对象与凸多边形相交

2015-3-23 20-13-17

图6.44 多边形对线性对象的裁剪

可以设线性对象的\(t\)在范围\([{{t}_{\min }},{{t}_{\max }}]\),若线性对象是直线,则\({{t}_{\min }}= – \infty \)和\({{t}_{\max }}= + \infty \);若线性对象是射线,则\({{t}_{\min }}=0\)和\({{t}_{\max }}=+\infty \);若线性对象是线段,则\({t_{\min }} = a,{t_{\max }} = b,a < b\),其中\(a\)和\(b\)是常数。这可能发生如图6.44所示的四种情况,图(a)计算得到的\({{t}_{in}}\)和\({{t}_{\max }}\)是裁剪线段的两个端点,但是图(b)~(d)得到的并不是裁剪线段,或者\({{t}_{in}}\)小于\({{t}_{\min }}\),或者\({{t}_{out}}\)大于\({{t}_{\max }}\)。因此,在求出线性对象与多边形相交的\({{t}_{in}}\)和\({{t}_{out}}\)后,还需要增加对\(t\)值限定范围的判断,可以采用如下等式来计算:

\[\begin{array}{l}{t_{in}}{\rm{ }} = \max \{ {t_{in}},{\rm{ }}{t_{\min }}\} \\{t_{out}} = \min \{ {t_{out}},{t_{\max }}\} \end{array} \tag{6.16}\]

Cyrus-Beck裁剪算法的伪码如下所示:

求线性对象\(L(t)=P+t\vec{d}\)与凸多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)的相交测试,其中\(t\in [{{t}_{\min }},{{t}_{\max }}]\),设凸多边形是逆时针顺序的,若相交,求出交点
return ({交点个数})
1.    \({{t}_{in}}={{t}_{\min }};\)
2.    \({{t}_{out}}={{t}_{\max }};\)
3.    for 多边形上的每条边\({{V}_{i}}{{V}_{i+1}}\)
4.           \(e={{V}_{i+1}}-{{V}_{i}}\);
5.           \(\vec{n}=({{e}_{y}},-{{e}_{x}})\);
6.           \(num=\vec{n}\cdot ({{V}_{i}}-P)\);
7.           \(den=\vec{n}\cdot \vec{d}\);
8.           if \(den\prec 0\), then                          //射线进入凸多边形
9.                  \(t=num/den\);      
10.                 if \(t\succ {{t}_{out}}\), then
11.                        return 0;
12.                 else if \(t\succ {{t}_{in}}\), then
13.                        \({{t}_{in}}=t\);
14.                 end if;
15.          else if \(den\succ 0\), then                   //射线离开凸多边形
16.                 \(t=num/den\);
17.                 if \(t\prec {{t}_{\operatorname{in}}}\), then
18.                        return 0;
19.                 else if \(t\prec {{t}_{out}}\), then
20.                        \({{t}_{out}}=t\);
21.                 end if;
22.          else if \(num\prec 0\), then
23.                 return 0;
24.          end if;
25.   end for;
26    \({{Q}_{1}}=P+{{t}_{in}}\vec{d}\);                                    //线性对象上,范围\([{{t}_{in}},{{t}_{out}}]\)内的线段在凸多边形内
27.   if \({{t}_{in}}=={{t}_{out}}\), then
28.          return 1;
29.   end if;
30.   \({{Q}_{2}}=P+{{t}_{out}}\vec{d}\);
31.   return 2;

2015-3-23 20-13-27

图6.45 射线和凸多边形的Cyrus-Beck裁剪算法

以图6.45所示为例,来解释Cyrus-Beck裁剪算法。求多边形对射线\({{L}_{1}}(t)={{P}_{1}}+t{{\vec{d}}_{1}}\)的裁剪,初始化\({{t}_{in}}=0\)和\({{t}_{out}}= + \infty \);对于边\(\overline{{{V}_{0}}{{V}_{1}}}\),射线进入多边形,计算出\({{t}_{1}}\)值,由于\(0={{t}_{in}}\prec {{t}_{1}}\prec {{t}_{out}}+\infty \),更新\({{t}_{in}}={{t}_{1}}\);对于边\(\overline{{{V}_{1}}{{V}_{2}}}\),可得\(\vec{n}\cdot \vec{d}=0\),两条线性对象平行,且\(\vec{n}\cdot ({{V}_{i}}-P)\succ 0\),算法继续;对于边\(\overline{{{V}_{2}}{{V}_{3}}}\),射线离开多边形,计算出\({{t}_{2}}\)值,由于\({{t}_{1}}={{t}_{in}}\prec {{t}_{2}}\prec {{t}_{out}}=+\infty \),更新\({{t}_{out}}={{t}_{2}}\);对于边\(\overline{{{V}_{3}}{{V}_{4}}}\),射线离开多边形,计算出\({{t}_{3}}\)值,由于\({{t}_{1}}={{t}_{in}}\prec {{t}_{3}}\prec {{t}_{out}}={{t}_{2}}\),更新\({{t}_{out}}={{t}_{3}}\);对于边\(\overline{{{V}_{4}}{{V}_{0}}}\),射线进入多边形,计算出\({{t}_{4}}\)值,由于\({{t}_{4}}\succ {{t}_{out}}={{t}_{3}}\),射线与多边形不相交,算法结束。

现在考虑求多边形\({{L}_{2}}(t)={{P}_{2}}+s{{\vec{d}}_{2}}\)的裁剪,初始化\({{s}_{in}}=0\)和\({{s}_{out}}=+\infty \);对于边\(\overline{{{V}_{0}}{{V}_{1}}}\),射线进入多边形,计算出\({{s}_{1}}\)值,由于\(0={{s}_{in}}\prec {{s}_{1}}\prec {{s}_{out}}+\infty \),更新\({{s}_{in}}={{s}_{1}}\);对于边\(\overline{{{V}_{1}}{{V}_{2}}}\),射线离开多边形,计算出\({{s}_{2}}\)值,由于\({{s}_{1}}={{s}_{in}}\prec {{s}_{1}}\prec {{s}_{out}}+\infty \),更新\({{s}_{out}}={{s}_{2}}\);对于边\(\overline{{{V}_{2}}{{V}_{3}}}\),射线离开多边形,计算出\({{s}_{3}}\)值,由于\({{s}_{3}}\succ {{s}_{in}}={{s}_{1}}\)且\({{s}_{3}}\succ {{s}_{out}}={{s}_{2}}\),不更新\({{s}_{in}}\)和\({{s}_{out}}\);对于边\(\overline{{{V}_{3}}{{V}_{4}}}\),可得\(\vec{n}\cdot \vec{d}=0\),两条线性对象平行,且\(\vec{n}\cdot ({{V}_{i}}-P)\succ 0\),算法继续;对于边\(\overline{{{V}_{4}}{{V}_{0}}}\),射线进入多边形,计算出\({{s}_{4}}\),由于\({{s}_{4}}\prec {{s}_{in}}={{s}_{1}}\)且\({{s}_{4}}\prec {{s}_{out}}={{s}_{2}}\),不更新\({{s}_{in}}\)和\({{s}_{out}}\)。至此,遍历完所有的凸多边形上所有的边,射线上\( [{{s}_{1}},{{s}_{2}}]\)之间的线段在凸多边形区域内,算法结束。

6.8.2. 二分法

问题描述:直线\(L(t)=P+t\vec{d}\)与凸多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)的相交测试,设凸多边形逆时针顺序的。

如果只要判断直线与凸多边形是否相交,不需要求出交点,那么只需判断直线与凸多边形的距离是否为零,如果为零,则相交,否则,不相交。但是,如果需要求出交点,我们可以基于第6.6节求凸多边形的极点的算法,如图6.46所示,计算出直线的法向量\(\vec{n}\),保证顶点\({{V}_{0}}\)在法向量的另一侧,求出凸多边形\({\rm P}\)上沿着方向\(\vec{n}\)的最大极点\({{V}_{k}}\)。设点到直线的有符号距离记为\(dist(V)=\vec{n}\cdot (V-P)\),则\(dist({{V}_{k}})\)表示极点\({{V}_{k}}\)到直线\(L\)的有符号距离,如果\(dist({{V}_{k}})\prec 0\),则直线与凸多边形不相交;如果\(dist({{V}_{k}})=0\),则直线与凸多边形相交于点\({{V}_{k}}\);否则,直线与凸多边形有两个交点,这两个交点分别在多边形链\(\{{{V}_{0}},{{V}_{1}},\cdots ,{{V}_{k}}\}\)和\(\{{{V}_{k}},{{V}_{k+1}},\cdots ,{{V}_{0}}\}\)上。

2015-3-23 20-13-38

图6.46 直线与凸多边形的相交

2015-3-23 20-13-47

图6.47 直线与多边形链的相交

设多边形链\(\{{{V}_{left}},{{V}_{left+1}},\cdots ,{{V}_{right}}\}\)与直线\(L\)有且只有一个交点,如图6.47所示,基于二分查找的原理,令\(mid=(left+right)/2\),如果\(dist({{V}_{mid}})=0\),那么\({{V}_{mid}}\)就是交点;如果\(dist({{V}_{mid}})\)与\(dist({{V}_{left}})\)同号,那么交点在顶点\({{V}_{mid}}\]与\({{V}_{right}}\)之间,则\(left=mid\);否则,交点在顶点\({{V}_{left}}\)与\({{V}_{mid}}\)之间,则\(right=mid\)。重复这个过程,直至\(left+1=right\)为止,这个子算法的复杂度为\(O(\log n)\)。伪码如下所示:

BINARY_SEARCH(\(L,{\rm P},min,max\))
/*\(L\)表示直线,它的参数方程表示为\(L(t)=P+t\vec{d}\),\({\rm P}\)表示凸多边形,\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \),\(min\)和\(max\)表示顶点的索引值,规定二分查找的范围*/
return ({交点})
1.      \(\vec{n}=(-{{\vec{d}}_{y}},{{\vec{d}}_{x}})\);
2.    \(r=-\vec{n}\cdot P\);
3.    \(left=min\);
4.    \(right=max\);
5.    \(dis{{t}_{1}}=\vec{n}\cdot {{V}_{left}}+r\);
6.    if \(dis{{t}_{1}}==0\), then
7.           return \({{V}_{left}}\);
8.    end if;
9.    while(\(left+1\ne right\))
10.          \(mid=(left+mid)/2\);
11.          \(dis{{t}_{2}}=\vec{n}\cdot {{V}_{mid}}+r\);
12.          if \(dis{{t}_{2}}==0\), then
13.                 return \({{V}_{\operatorname{mid}}}\);
14.          else if (\(dis{{t}_{1}}\succ 0\)&&\(dis{{t}_{2}}\succ 0\)) || (\(dis{{t}_{1}}\prec 0\]&&\(dis{{t}_{2}}\prec 0\)), then
15.                 \(left=mid\);
16.          else
17.                 \(right=mid\);
18.          end if;
19.   end while;
20.   return LINE_INTER_SEGMENT(\(L,\overline{{{V}_{left}}{{V}_{right}}}\))           //计算直线\(L\)与线段\(\overline{{{V}_{left}}{{V}_{right}}}\)的交点

求凸多边形在指定方向的极点的复杂度为\(O(\log n)\),求多边形链与直线的交点的二分查找法的算法复杂度也是\(O(\log n)\),因此求直线与凸多边形交点的算法复杂度为\(O(\log n)\),算法伪码如下所示:

直线\(L(t)=P+t\vec{d}\)与凸多边形\({\rm P} = \{ {V_0},{V_1},…,{V_{n – 1}}\} \)的相交测试,设凸多边形逆时针顺序的,若相交,求出交点
return ({交点个数})
1.    \(\vec{n}=(-{{\vec{d}}_{y}},{{\vec{d}}_{x}})\);
2.    if \(\vec{n}\cdot ({{V}_{0}}-P)\succ 0\), then
3.           \(\vec{n}=-\vec{n}\);
4.    end if;
5.      k = EXTREME_OF_CONVEX(\({\rm{P}}\),\(\vec{n}\));               //获取多边形\({\rm{P}}\)上,方向是\(\vec{n}\)的最大极点
6.      \(d=\vec{n}\cdot ({{V}_{k}}-P)\);
7.      if \(d==0\), then
8.           \({{Q}_{1}}={{P}_{k}}\);
9.           if \(\vec{n}\cdot ({{V}_{k+1}}-P)==0\), then                         //直线\(L\)与边\(\overline{{{V}_{k}}{{V}_{k+1}}}\)重合
10.                 \({{Q}_{2}}={{V}_{k+1}}\);
11.                 return 2;
12.          else if \(\vec{n}\cdot ({{V}_{k-1}}-P)==0\), then                   //直线\(L\)与边\(\overline{{{V}_{k-1}}{{V}_{k}}}\)重合
13.                 \({{Q}_{2}}={{V}_{k-1}}\);
14.                 return 2;
15.          else                                                          //直线\)L\)与经过点\({{V}_{k}}\)
16.                 return 1;
17.          end if;
18.   else if \(d\prec 0\), then
19.          return 0;
20.   else
21.          \({{Q}_{1}}=\)BINARY_SEARCH(\(L,{\rm{P}},0,k\));
22.          \({{Q}_{2}}=\)BINARY_SEARCH(\(L,{\rm{P}},k,n\));
23.          return 2;
24.   end if;

spacer

Leave a reply