浏览量:97

7.6. 凸多边形间的距离

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

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

7.6. 凸多边形间的距离

问题描述:给定两个互不相交的凸多边形\(P = \{ {p_0},{p_1}, \cdots ,{p_{n – 1}}\} \)和\({\mathop{\rm Q}\nolimits}  = \{ {q_0},{q_1}, \cdots ,{q_{m – 1}}\} \),求它们之间的最小距离,设两个凸多边形都是逆时针顺序的。

两个凸多边形上的最小距离,可以用等式表示为

\[dis{t_{\min }}(P,Q) = \min \{ dist(p,q),\forall p \in P,\forall p \in {\mathop{\rm Q}\nolimits} \} \]

2015-3-23 21-42-11

图7.13 凸多边形间的最小距离

假设,两个凸多边形\(P\)和\(\operatorname{Q}\)是分离的,则有

定理7.6.   给定两个凸多边形\(P\)和\(\operatorname{Q}\),则存在一组点对\((p,q)\),其中\(p \in P,q \in {\rm{Q}}\),使得\({{\operatorname{dist}}_{min}}(P,Q)=dist(p,q)\),那么点\(p\)和点\(q\)只能是对应凸多边形的顶点或者在其边上。

证明用反证法证明,凸多边形间的最小距离\(dis{{t}_{\min }}(P,Q)\)由点对\( (p,q)\)确定,设点\(q\)在凸多边形\(\operatorname{Q}\)的内部,如图7.13所示,连接线段点\(p\)和点\(q\),线段\(\overline{pq}\)与凸多边形\(\operatorname{Q}\)相交于点\(q’\),显然有\(\operatorname{dist}(p,q)\succ dist(p,q’)\),这与点对\((p,q)\)是两凸多边形的最小距离的条件矛盾。所以点\(q\)不可能是凸多边形\(\operatorname{Q}\)的内部点,只能是它的顶点或者在边上。同理,可以证明点\(q\)也只能是凸多边形\(P\)的顶点或者在它的边上。

因此,确定两凸多边形间最小距离的两个点\((p,q)\)只能是下面3种情况,如图7.14所示:

  1. 点-点对踵对,点\(p\)是\(P\)的顶点,点\(q\)是\(\operatorname{Q}\)的顶点,如图(a)所示;
  2. 点-边对踵对,点\(p\)是\(P\)的顶点,点\(q\)在\(\operatorname{Q}\)的边上,或者相反,如图(b)所示;
  3. 边-边对踵对,点\(p\)和点\(q\)分别在\(P\)和\(\operatorname{Q}\)的边,如图(c)所示,边-边对踵对可以看作是点-边对踵对来计算。

2015-3-23 21-42-24

图7.14 \((p,q)\)的3种情况

旋转测径法就是通过旋转支撑线,找到最小距离的对踵对,伪码如下所示:

给定两个互不相交的凸多边形\(P=\{{{p}_{0}},{{p}_{1}},\cdots ,{{p}_{n-1}}\}\)和\(\operatorname{Q}=\{{{q}_{0}},{{q}_{1}},\cdots ,{{q}_{m-1}}\}\),求它们之间的最小距离,设两个凸多边形都是逆时针顺序的
1.    \({{k}_{\min }}=0,{{k}_{\max }}=0\);
2.    for( i = 1 ; i < n ; ++i )                                     //求凸多边形\(P\)上y值最小的点
3.           if \({{p}_{i}}.y\prec {{p}_{{{k}_{\min }}}}.y\), then
4.                  \({{k}_{\min }}=i\);
5.           end if;
6.    end for;
7.    for( i = 1 ; i < m ; ++i )                                    //求凸多边形\(\operatorname{Q}\)上y值最大的点
8.           if \({{p}_{i}}.y\succ {{p}_{{{k}_{\max }}}}.y\), then
9.                  \({{k}_{\max }}=i\);
10.          end if;
11.   end for;
12.   \(coun{{t}_{P}}=0,coun{{t}_{Q}}=0;\)
13.   \(dis{{t}_{\min }}=+\infty \);
14.   \(i={{k}_{\min }},j={{k}_{\max }}\);
15.   do
16.          \({{e}_{1}}={{p}_{next(i)}}-{{p}_{i}}\);
17.          \({{e}_{2}}={{q}_{next(j)}}-{{q}_{j}}\);
18.          \(d={{e}_{1}}\times {{e}_{2}}\);
19.          if d < 0, then
20.                 dist = COMPUTE_ANTI_DIST(\({{p}_{i}},{{p}_{next(i)}},{{q}_{j}}\));
21.                 \(dis{{t}_{\min }}=min\{dist,dis{{t}_{\min }}\}\);
22.                 \(i=next(i)\);
23.                 \(coun{{t}_{P}}+=1\);
24.          else
25.                 dist = COMPUTE_ANTI_DIST(\({{q}_{j}},{{q}_{next(j)}},{{p}_{i}}\));
26.                 \(dis{{t}_{\min }}=min\{dist,dis{{t}_{\min }}\}\);
27.                 \(i=next(i)\);
28.                 \(coun{{t}_{Q}}+=1\);
29.          end if;
30.   while(\(coun{{t}_{P}}\le n\) && \(coun{{t}_{Q}}\le m\));
31.   return \(dis{{t}_{\min }}\);

2015-3-23 21-42-37

图7.15 点-边对踵对之间的距离

函数COMPUTE_ANTI_DIST(\({{p}_{1}},{{p}_{2}},q\))用于计算点-边对踵对之间的距离,即计算点\(q\)到边\(\overline{{{p}_{1}}{{p}_{2}}}\)的距离。如图7.15所示,如果点\(q\)到边\(\overline{{{p}_{1}}{{p}_{2}}}\)所在的直线的投影点在边上,则点\(q\)到边\(\overline{{{p}_{1}}{{p}_{2}}}\)的距离就是点-边对踵对之间的距离;否则,点\(q\)到点\({{p}_{2}}\)的距离为所求的距离。

函数COMPUTE_ANTI_DIST(\({{p}_{1}},{{p}_{2}},q\))的算法伪码如下所示:

COMPUTE_ANTI_DIST(\({{p}_{1}},{{p}_{2}},q\))
1.    \(\vec{d}={{p}_{2}}-{{p}_{1}}\);
2.    \({{\vec{v}}_{1}}=q-{{p}_{1}}\);
3.    \({{\vec{v}}_{2}}=q-{{p}_{2}}\);
4.    \({{t}_{1}}=\vec{d}\cdot {{\vec{v}}_{1}}\);
5.    \({{t}_{2}}=\vec{d}\cdot {{\vec{v}}_{2}}\);
6.    if (\({{t}_{1}}\le 0\)&&\({{t}_{1}}\ge 0\)) || (\({{t}_{1}}\ge 0\)&&\({{t}_{1}}\le 0\)), then
7.           \(\vec{n}=(-{{\vec{d}}_{y}},{{\vec{d}}_{x}})\);
8.           \(s=-\vec{n}\cdot {{p}_{1}}\);
9.           return \(\left\| \vec{n}\cdot q+s \right\|/\left\| {\vec{n}} \right\|\);
10.   else
11.          return \(\left\| q-{{p}_{1}} \right\|\);
12.   end if;

spacer

Leave a reply