浏览量:445

7.4. 最小面积包围矩形

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

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

7.4. 最小面积包围矩形

问题描述:给定一组点集\(\{{{p}_{0}},{{p}_{1}},\cdots ,{{p}_{n-1}}\}\),求一个矩形,满足条件:(1)点集在矩形内部;(2)矩形的面积最小。

首先求点集的凸多边形,易知,包围凸多边形的矩形一定包含整个点集,这一子步骤的复杂度是\(O(n\log n)\)。接着,可以利用旋转测径法,计算凸包的最小面积包围矩形,这一子步骤的复杂度是\(O(n)\)。显然,整个算法的复杂度受凸包算法的限制。

现在考虑最小面积包围矩形与凸多边形的关系,可以得出结论:

定理7.4.   最小面积的包围矩形的一条边与凸多边形的一条边是重合的。

2015-3-23 21-41-31

图7.10 包围矩形的例子

证明:用反证法来证明,给定一个凸多边形\({\rm P}\),若包围矩形的任意一条边与多边形都不重合,它仍可能是最小面积矩形。令矩形与多边形相切的四个顶点分别是\({{p}_{i}},{{p}_{j}},{{p}_{k}},{{p}_{l}}\),如图7.10所示。令包围矩形的面积是\(A\],则有\(A={{l}_{0}}{{l}_{1}}\)。进一步,令\({{p}_{i}}\)和\({{p}_{k}}\)的距离与\({{p}_{j}}\)和\({{p}_{l}}\)的距离分别用\({{d}_{i,k}},{{d}_{j,l}}\)表示,则有

\[\left\{ \begin{array}{l}{l_0} = {d_{i,k}} \cdot cos{\alpha _k}\\{l_1} = {d_{j,l}} \cdot cos{\alpha _l}\end{array} \right.\]

将矩形沿着逆时针方向旋转\(\eta \)角(\(\eta \)是正值,保证\({{p}_{i}},{{p}_{j}},{{p}_{k}},{{p}_{l}}\)仍是新的矩形的相切点),边长\({{l}_{0}},{{l}_{1}}\)会发生变化,这可以分成两种情况:(1)同时变长或变短;(2)一条边变长,另一条变短。

情况(1),若沿着逆时针方向旋转\(\eta \)角,得到新的边长\({{l}_{0}}’,{{l}_{1}}’\) (\({{l}_{0}}’\prec {{l}_{0}},{{l}_{1}}’\prec {{l}_{1}}\))缩短,则面积\(A’={{l}_{0}}'{{l}_{1}}’\prec {{l}_{0}}{{l}_{1}}=A\),能得到面积更小的矩形;相反,若新边的长度都增加了,则将矩形沿顺时针方向旋转一定的角度,得到的新边一定变短,同样能得到面积更小的矩形。

情况(2),矩形的旋转,导致一条边变长,另一条变短,设矩形沿逆时针方向旋转\(\delta \](\(\delta \)是正值),\({{l}_{0}}\)变长,\({{l}_{1}}\)变短,有

\({A_{CC}} = {l_0}'{l_1}’\left\{ {\begin{array}{*{20}{c}}{{l_0}’ = {d_{i,k}}\cos ({\alpha _k} – \delta )}\\{{l_1}’ = {d_{j,l}}\cos ({\alpha _l} + \delta )}\end{array}} \right.\)

则矩形沿顺时针方向旋转\(\delta \) (\(\delta \)是正值),\({{l}_{0}}\)变短,\({{l}_{1}}\)变长,有

\[{A_C} = {l_0}”{l_1}”\left\{ {\begin{array}{*{20}{c}}{{l_0}” = {d_{i,k}}\cos ({\alpha _k} + \delta )}\\{{l_1}” = {d_{j,l}}\cos ({\alpha _l} – \delta )}\end{array}} \right.\]

现在对比\({{A}_{C}},{{A}_{CC}}\)与\(A\)的大小关系,有

\[\frac{{{A_{CC}}}}{A} = {\cos ^2}\delta + (\tan {\alpha _k} – \tan {\alpha _l})\sin \delta \cos \delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta \]

\[\frac{{{A_C}}}{A} = {\cos ^2}\delta – (\tan {\alpha _k} – \tan {\alpha _l})\sin \delta \cos \delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta \]

若\(\frac{{{A_{CC}}}}{A} \prec 1\),则逆时针旋转矩形,可以得到面积更小的矩形;否则\(\frac{{{A_{CC}}}}{A} \ge 1\),有

\[\begin{array}{l}{\rm{ }}{\cos ^2}\delta + (\tan {\alpha _k} – \tan {\alpha _l})\sin \delta \cos \delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta \le 1\\ \Leftrightarrow – (\tan {\alpha _k} – \tan {\alpha _l})\sin \delta \cos \delta \le {\cos ^2}\delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta – 1\\ \Leftrightarrow \frac{{{A_C}}}{A} \le 2({\cos ^2}\delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta ) – 1\\ \Leftrightarrow \frac{{{A_C}}}{A} \le 2(1 – si{n^2}\delta – \tan {\alpha _k}\tan {\alpha _l}{\sin ^2}\delta ) – 1\\ \Leftrightarrow \frac{{{A_C}}}{A} \le 1 – 2(1 + \tan {\alpha _k}\tan {\alpha _l}){\sin ^2}\delta \end{array}\]

因为\(0\prec {{\alpha }_{k}},{{\alpha }_{l}}\prec \frac{\pi }{2}\),所以\(\frac{{{A}_{C}}}{A}\prec 1\),此时,顺时针旋转矩形,可以得到面积更小的矩形。

综上两种情况,我们可以最小面积的包围矩形的一条边与凸多边形的一条边是重合的。

 

由定理7.4可知,我们首先需要求出一个点-边对踵对,确定矩形的一组对边,该边的垂直方向就是另一组边的支撑线的方向,因此也可以较容易地求出另一组对边。

求凸多边形的最小面积包围矩形的伪码如下所示:

求凸多边形\({\rm P} = \{ {p_0},{p_1}, \cdots ,{p_{n – 1}}\} \)的最小面积包围矩形,设凸多边形\({\rm P}\]是逆时针方向的,其中,\({p_n} = {p_0},{\theta _n} = {\theta _0}\)
1.    \({{i}_{\min }}=0\);
2.    \(\vec{d}=\left( {{p}_{imin+1}}-{{p}_{i\min }} \right),\vec{d}=\vec{d}/\left\| {\vec{d}} \right\|,\vec{n}=(-{{\vec{d}}_{y}},{{\vec{d}}_{x}})\);
3.    \({{n}_{\max }}=-\infty ,{{d}_{\min }}=+\infty ,{{d}_{\max }}=-\infty \);
4.    \(area=+\infty \);
5.    for( i = 0 ; i < n ; ++i )         //求出初始边水平方向上投影最小的点jmin,最大的点jmax
6.           \(\vec{t}={{p}_{i}}-{{p}_{a}}\);                     //垂直方向上投影最大的点imax
7.           \(s=\vec{d}\cdot \vec{t}\);
8.           if \(s\prec {{d}_{\min }}\), then
9.                  \({{d}_{\min }}=s,{{j}_{min}}=i\);
10.          end if;
11.          if \(s\succ {{d}_{\max }}\), then
12.                 \({{d}_{\max }}=s,{{j}_{max}}=i\);
13.          end if;
14.          \(s=\vec{n}\cdot \vec{t}\);
15.          if \(s\succ {{n}_{\max }}\), then
16.                 \({{n}_{\max }}=s,{{i}_{max}}=i\);
17.          end if;
18.   end for;
19.   for ( i=0 ; i<n ; i++ )
20.          计算边与支撑线的夹角\({{\theta }_{{{i}_{\min }}+1}},{{\theta }_{{{i}_{\max }}}},{{\theta }_{{{j}_{\min }}}},{{\theta }_{{{j}_{\max }}}}\);
21.          最小夹角的索引值为k;
22.          if k==0, then
23.                 return;
24.          end if;
25.          更新\({{i}_{\min }},{{i}_{\max }},{{j}_{\min }},{{j}_{\max }}\)四个索引值;
26.          \(\vec{d}=\left( {{p}_{{{i}_{min}}+1}}-{{p}_{{{i}_{\min }}}} \right),\vec{d}=\vec{d}/\left\| {\vec{d}} \right\|,\vec{n}=(-{{\vec{d}}_{y}},{{\vec{d}}_{x}})\);
27.          \({{l}_{0}}=\vec{d}\cdot \left( {{p}_{{{j}_{\max }}}}-{{p}_{{{j}_{\min }}}} \right),{{l}_{1}}=\vec{n}\cdot \left( {{p}_{{{i}_{\max }}}}-{{p}_{{{i}_{\min }}}} \right)\);
28.          \(area=\min \{{{l}_{0}}\cdot {{l}_{1}},area\}\);
29.   end for;

2015-3-23 21-41-45

图7.11 计算凸多边形的最小面积包围矩形

如图7.11所示,实际上只需要对比角度的大小,因此只要得到角度的cos值,避免反三角函数的计算,cos值最大的角最小。例如求\({{\theta }_{{{i}_{\min }}+1}}\)的cos值,\(\cos {{\theta }_{{{i}_{\min }}+1}}=\vec{d}\cdot ({{p}_{{{i}_{\min }}+2}}-{{p}_{{{i}_{\min }}+1}})\),对于其它角度的计算也是类似的,特别得注意支撑线的方向。

算法第25步,更新\({{i}_{\min }},{{i}_{\max }},{{j}_{\min }},{{j}_{\max }}\)四个索引值,如何更新索引值呢?由于包围矩形旋转的角度是\({{\theta }_{k}}=\min \{{{\theta }_{{{i}_{\min }}+1}},{{\theta }_{{{i}_{\max }}}},{{\theta }_{{{j}_{\min }}}},{{\theta }_{{{j}_{\max }}}}\}\),可以保证点\({{p}_{{{i}_{\min }}+1}},{{p}_{{{i}_{\max }}}},{{p}_{{{j}_{\min }}}},{{p}_{{{j}_{\max }}}}\)仍是旋转后新矩形支撑线的接纳点。索引值的更新方法,如下等式所示:

\[\left\{ {\begin{array}{*{20}{l}}{{i_{\min }}’ = {i_{\min }} + 1,}&{{i_{\max }}’ = {i_{\max }},}&{{j_{\min }}’ = {j_{\min }},}&{{j_{\max }}’ = {j_{\max }},}&{if,k = {i_{\min }} + 1;}\\{{i_{\min }}’ = {i_{\max }},}&{{i_{\max }}’ = {i_{\min }} + 1,}&{{j_{\min }}’ = {j_{\max }},}&{{j_{\max }}’ = {j_{\min }},}&{if,k = {i_{\max }};}\\{{i_{\min }}’ = {j_{\min }},}&{{i_{\max }}’ = {j_{\max }},}&{{j_{\min }}’ = {i_{\min }} + 1,}&{{j_{\max }}’ = {i_{\max }},}&{if,k = {j_{\min }};}\\{{i_{\min }}’ = {j_{\max }},}&{{i_{\max }}’ = {j_{\min }},}&{{j_{\min }}’ = {i_{\max }},}&{{j_{\max }}’ = {i_{\min }} + 1,}&{if,k = {j_{\max }};}\end{array}} \right.\]

spacer

Leave a reply